[SCIP] How to get the Lower Bound while implementing the Branching Rule?
Gregor Hendel
hendel at zib.de
Thu Mar 22 10:21:31 CET 2018
Dear Matheus,
constraints are the most fundamental concept of SCIP. They are far more
general than matrix-based restrictions of the search domain. A
constraint may be representable only by a set of
linear inequalities (such as an "and"-constraint on binary variables),
or not completely linearly representable at all (nonlinear constraints).
A constraint will, during the solution process, add as much of its
linear representation to the
LP relaxation as needed.
As long as you solve linearly constrained problems, the differences
between constraints and rows are negligible,
there is usually a 1-1 correspondence.
If you are interested, you find more information in the original
publication "SCIP: Solving Constraint Integer Programs" by Tobias
Achterberg.
Kind regards,
Gregor
Am 21.03.2018 um 23:00 schrieb Matheus Ota:
> Hi,
>
> I followed the src/scip/branch_multaggr.c and I guess it is working
> fine now! It turns out I have mistaken the SCIPbacktrackProbing
> function. The second argument need to be the depth of the node I want
> to go back to, and not the number of steps up I want to go.
> Can I ask another thing? Whats the difference between a SCIP_ROW and a
> SCIP_CONS? Because the way I think of each constraint is translated
> into a row in the problem formulation.
>
> Thanks,
> Matheus
>
> 2018-03-21 6:42 GMT-03:00 Gerald Gamrath <gamrath at zib.de
> <mailto:gamrath at zib.de>>:
>
> Dear Matheus,
>
> if you create your constraints as linear constraints, and not as
> rows, you cannot add them with SCIPaddRowProbing, but should
> rather use SCIPaddConsNode and provide the probing node as the
> node to add the constraint to.
>
> I would recommend to have a look at the multi-aggregated branching
> rule (src/scip/branch_multaggr.c), which does something very
> similar to what you want to do.
>
> Best,
> Gerald
>
>
> On 21.03.2018 00:26, Matheus Ota wrote:
>> Hi,
>>
>> Thanks for the fast reply! I followed what you said, but I guess
>> I'm doing something wrong, can you help me to figure it out?
>>
>> So first I enclosed the part of the code that I want to compute
>> the lower bounds in SCIPstartProbing(scip) and SCIPendProbing(scip).
>>
>> Then I call SCIPnewProbingNode(scip), create the constraint1 and
>> add it with SCIPaddRowProbing(scip, constraint1). I then solve
>> the probing node with SCIPsolveProbingLP(scip, -1, &lperror,
>> &cutoff), get the lower bound with SCIPgetLPObjval(scip) and got
>> back to the parent with SCIPbacktrackProbing(scip, 1).
>>
>> This same process is then repeated imposing constraint2 in the
>> problem.
>>
>> Can you tell me if this is the right way to do it? The code is
>> not working as it was before adding the branching rule and I'm
>> having some difficulties in understanding how to use the probing
>> mode correctly.
>>
>> Thanks again,
>> Matheus
>>
>>
>> 2018-03-20 5:52 GMT-03:00 Gregor Hendel <hendel at zib.de
>> <mailto:hendel at zib.de>>:
>>
>> Dear Matheus,
>>
>> this sounds like an application of the SCIP probing mode,
>> which allows to explore some tentative children before
>> branching. Please have a look at the documentation of the
>> probing mode:
>>
>> http://scip.zib.de/doc-5.0.1/html/group__PublicProbingMethods.php
>> <http://scip.zib.de/doc-5.0.1/html/group__PublicProbingMethods.php>
>>
>> Probing mode supports local constraints at the tentative
>> node, and solve the corresponding LP relaxation.
>>
>> You can then retrieve the LP solution objective using
>> SCIPgetLPObjval(), see also
>>
>> http://scip.zib.de/doc-5.0.1/html/group__PublicLPMethods.php
>> <http://scip.zib.de/doc-5.0.1/html/group__PublicLPMethods.php>
>>
>> for further information.
>>
>> Happy probing,
>> Gregor
>>
>>
>>
>> Am 19.03.2018 um 21:45 schrieb Matheus Ota:
>>> Hi,
>>>
>>> Im trying to use SCIP to implement a Branch-Cut-and-Price
>>> for the VRP. For now Im focusing only on the Branch-and-Cut
>>> part, using the CVRPSEP package
>>> (http://econ.au.dk/research/researcher-websites/jens-lysgaard/cvrpsep/
>>> <http://econ.au.dk/research/researcher-websites/jens-lysgaard/cvrpsep/>).
>>> I already added the cuts and my program is able to solve
>>> some simple instances, in order to increase its performance
>>> I need to implement custom branching rules.
>>>
>>> The branching rule works this way: it first select a few
>>> subsets of the set of vertexes in the graph and impose a few
>>> constraints on them. It then computes the lower bound
>>> (solving the relaxation) for each child node and uses these
>>> values to choose the node to branch on. Could you please
>>> give me some information about of how I can get the lower
>>> bound on the branching rule callback? Or maybe a better way
>>> of doing this or something similar?
>>>
>>> Thanks,
>>> Matheus
>>>
>>>
>>> _______________________________________________
>>> Scip mailing list
>>> Scip at zib.de <mailto:Scip at zib.de>
>>> https://listserv.zib.de/mailman/listinfo/scip
>>> <https://listserv.zib.de/mailman/listinfo/scip>
>>
>>
>> _______________________________________________
>> Scip mailing list
>> Scip at zib.de <mailto:Scip at zib.de>
>> https://listserv.zib.de/mailman/listinfo/scip
>> <https://listserv.zib.de/mailman/listinfo/scip>
>>
>>
>>
>>
>> _______________________________________________
>> Scip mailing list
>> Scip at zib.de <mailto:Scip at zib.de>
>> https://listserv.zib.de/mailman/listinfo/scip
>> <https://listserv.zib.de/mailman/listinfo/scip>
>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de <mailto:Scip at zib.de>
> https://listserv.zib.de/mailman/listinfo/scip
> <https://listserv.zib.de/mailman/listinfo/scip>
>
>
>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20180322/b026f86d/attachment.html>
More information about the Scip
mailing list