[SCIP] How to get the Lower Bound while implementing the Branching Rule?

[Matheus Ota]

Hi,

Thanks for the clarification. I also came with another question while
implementing the branching rule. I have a constraint handler responsible
for subtour removal on the graph, despite this, a solution with a subtour
is going into the SCIP_DECL_BRANCHEXECPS method of the branching rule.
Reading the documentation it says that the BRANCHEXECPS method will only be
called if the infeasibility could not be resolved in the callback methods
CONSENFOLP <http://scip.zib.de/doc/html/CONS.php#CONSENFOLP> and CONSENFOPS
<http://scip.zib.de/doc/html/CONS.php#CONSENFOPS>. So while I was debugging
this, it seems that the method called before entering the branching rule
was responsible only for checking the feasibility of the solution, not
actually solving it. And the checking is returning correctly: that the
current solution is infeasible.

My code is working right now but I'm also checking the feasibility of the
solution on the branching callback. If it is infeasible, I do not create
any child and the cuts are then properly added by the constraint handler
callback.

Thanks again,
Matheus

2018-03-22 6:21 GMT-03:00 Gregor Hendel <hendel at zib.de>:

> 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>:
>
>> 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>:
>>
>>> 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
>>>
>>> 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
>>>
>>> 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-lysgaar
>>> d/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 listScip at zib.dehttps://listserv.zib.de/mailman/listinfo/scip
>>>
>>>
>>>
>>> _______________________________________________
>>> Scip mailing list
>>> Scip at zib.de
>>> https://listserv.zib.de/mailman/listinfo/scip
>>>
>>>
>>
>>
>> _______________________________________________
>> Scip mailing listScip at zib.dehttps://listserv.zib.de/mailman/listinfo/scip
>>
>>
>>
>> _______________________________________________
>> Scip mailing list
>> Scip at zib.de
>> https://listserv.zib.de/mailman/listinfo/scip
>>
>>
>
>
> _______________________________________________
> Scip mailing listScip at zib.dehttps://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/20180323/ae414b59/attachment.html>