[SCIP] Branching on optimal solution
Matheus Ota
matheusota at gmail.com
Wed May 23 22:15:12 CEST 2018
Hi All,
Nevermind, I erased the SCIP_DECL_BRANCHEXECLP accidentally. Sorry about
bothering you guys for that.
Thanks,
Matheus
2018-05-22 15:49 GMT-03:00 Matheus Ota <matheusota at gmail.com>:
> Oh, and when I said the solution that got to SCIP_DECL_CONSENFOPS was not
> integer, I have mistaken the SCIP_DECL_CONSENFOLP with the
> SCIP_DECL_CONSENFOPS method, sorry about that.
> The SCIP_DECL_CONSENFOPS is not even being called anymore. The solutions
> that gets to *SCIP_DECL_CONSENFOLP* is not integer.
>
> Thanks,
> Matheus
>
> 2018-05-22 15:38 GMT-03:00 Matheus Ota <matheusota at gmail.com>:
>
>> Hi Gerald and Ambros,
>>
>> Thanks for the help. I did some changes:
>>
>> - The epsilon that I used in my code to check for integrality was
>> different from the one used by SCIP (10^-6?)
>> - On the SCIP_DECL_CONSENFOLP, if the solution is not feasible, it tries
>> to generate cuts and set the result to SCIP_SEPARATED
>> - On the SCIP_DECL_CONSENFOPS, if the solution is not feasible, it sets
>> the result to SCIP_SOLVELP.
>>
>> The SCIP_DECL_CONSCHECK was not changed.
>>
>> And here is the log for the branching rules:
>> Branching Rules : ExecTime SetupTime BranchLP BranchExt
>> BranchPS Cutoffs DomReds Cuts Conss Children
>> CVRPBranchingRule: 0.00 0.00 0
>> 0 0 0 0
>> 0 0 0
>> allfullstrong : 0.00 0.00
>> 0 0 0 0
>> 0 0 0 0
>> cloud : 0.00 0.00
>> 0 0 0 0
>> 0 0 0 0
>> distribution : 0.00 0.00
>> 0 0 0 0
>> 0 0 0 0
>> fullstrong : 0.00 0.00
>> 0 0 0 0
>> 0 0 0 0
>> inference : 0.00 0.00 0
>> 0 0 0
>> 0 0 0 0
>> leastinf : 0.00 0.00
>> 0 0 0 0
>> 0 0 0 0
>> mostinf : 0.00 0.00
>> 0 0 0 0
>> 0 0 0 0
>> multaggr : 0.00 0.00
>> 0 0 0 0
>> 0 0 0 0
>> nodereopt : 0.00 0.00
>> 0 0 0 0
>> 0 0 0 0
>> pscost : 0.00 0.00
>> 0 0 0 0
>> 0 0 0 0
>> random : 0.00 0.00
>> 0 0 0 0
>> 0 0 0 0
>> relpscost : 4.38 0.00
>> 112 0 0 0
>> 66 0 0 174
>>
>> So it seems it is not calling the "inference" branching anymore. But it
>> is still calling the "relpscost" branching instead of calling the
>> "CVRPBranchingRule" for the "BranchLP" column.
>>
>> How can I enforce it to call only the "CVRPBranchingRule"? This might
>> make the code slower, but I need to do so because in the future I will add
>> a pricer to implement a Branch-Cut-and-Price.
>> In order to keep the column generation easy, I need to branch only using
>> the rules defined in the "CVRPBranchingRule".
>>
>> Thanks,
>> Matheus
>>
>> 2018-05-22 9:51 GMT-03:00 Gerald Gamrath <gamrath at zib.de>:
>>
>>> Hi Matheus,
>>>
>>> let me add some comments:
>>>
>>> the "PS" in CONSENFOPS stands for pseudo solutions. Those are the
>>> solutions to the relaxation of the problem that omits all constraints. For
>>> this reason, each variable will be set to one of its bounds, depending on
>>> the sign of its objective coefficient. The pseudo solution is the
>>> backup-plan in SCIP, if the LP could not be solved (or provides no
>>> branching candidate).
>>>
>>> Therefore, each solution that arrives at SCIP_DECL_CONSENFOPS should be
>>> integer (bounds are integer for integer variables). How do you access the
>>> solution?
>>>
>>> Now suppose that you had numerical problems in the LP and the LP could
>>> not be solved to optimality. Then SCIP falls back enforcing the pseudo
>>> solution, as Ambros said, and potentially branching on it, if no constraint
>>> handler resolved the infeasibility in another way.
>>> In case of such numerical troubles, adding a cut to the LP is not an
>>> option, because SCIP dismissed the LP at that node anyway, so branching
>>> really needs to be performed on one of the unfixed integer variables.
>>> If your CVRP branching rule implements the BRANCHEXECPS , it should be
>>> called on such a solution, but if it does not want to branch on an unfixed
>>> variable with integer value, some other branching rule must step in and
>>> perform the branching, so that is inference branching in this case.
>>>
>>> I see another potential problem in your implementation, though: Even if
>>> the LP is solved to optimality, it may happen that you enter CONSENFOLP
>>> with an integer solution that violates some constraint that is not (yet)
>>> present in the LP. For example, separation may be limited to a certain
>>> number of rounds or stopped due to stalling. In that case, it might happen
>>> that a solution is given to CONSENFOLP that can be separated by a cut of a
>>> constraint handler. Then, the constraint handler should just do this in
>>> CONSENFOLP, and set the result to SCIP_SEPARATED. In general, a constraint
>>> handler should always try to resolve the infeasibility within the
>>> enforcement callback, it should avoid to just return INFEASIBLE: it already
>>> detected that (and why) the current solution is infeasible, why should it
>>> wait for another plugin to detect the same reason or possibly do a
>>> unrelated branching decision?
>>> Because what happen afterwards is that no branching can be performed on
>>> the LP solution because all variables are integral in the LP solution.
>>> Thus, the only chance for SCIP to continue is to branch on the pseudo
>>> solution.
>>>
>>> Best,
>>> Gerald
>>>
>>>
>>> On 22.05.2018 14:16, Matheus Ota wrote:
>>>
>>> Hi Ambros,
>>>
>>> What does SCIP_DECL_CONSENFOPS do in the case that the solution is
>>>> infeasible? If you only return SCIP_INFEASIBLE and no other constraint
>>>> handler takes some action, then the branching rules must be called to
>>>> resolve the infeasibility. In your case inference branching is called
>>>> twice.
>>>
>>>
>>> When the solution is infeasible, the SCIP_DECL_CONSENFOPS just set
>>> result as SCIP_INFEASIBLE and take no other action. After this, instead
>>> of calling the "inference branching", I would like SCIP to call the "CVRPBranchingRule"
>>> that I wrote.
>>>
>>> Arriving at the enfops callback probably means that the LP could not be
>>>> solved, typically due to numerical problems. If you only have integer
>>>> variables then in the worst case the subtree below is solved by complete
>>>> enumeration. But you seem to be lucky: inference branching is only called
>>>> twice on the pseudo solution, so either the subtree can be pruned early or
>>>> the numerical troubles disapppear after branching.
>>>
>>>
>>> But this is strange, because if the solution is integer and infeasible,
>>> then, since Im implementing a branch-and-cut, the constraint handler should
>>> be able to find a cut that separates this solution from the feasible set.
>>> Checking the solutions that arrive at SCIP_DECL_CONSENFOPS, then
>>> indeed, they are not integer solutions. So, instead of calling the "CVRPBranchingRule"
>>> to solve the integrality, it is calling the "inference branching".
>>>
>>> Thanks,
>>> Matheus
>>>
>>> 2018-05-22 2:51 GMT-03:00 Ambros Gleixner <gleixner at zib.de>:
>>>
>>>> Hi Matheus,
>>>>
>>>>
>>>> the SCIP_DECL_CONSENFOLP, SCIP_DECL_CONSENFOPS and SCIP_DECL_CONSCHECK
>>>>> check if the current solution is a feasible solution
>>>>>
>>>>
>>>> What does SCIP_DECL_CONSENFOPS do in the case that the solution is
>>>> infeasible? If you only return SCIP_INFEASIBLE and no other constraint
>>>> handler takes some action, then the branching rules must be called to
>>>> resolve the infeasibility. In your case inference branching is called
>>>> twice.
>>>>
>>>> Arriving at the enfops callback probably means that the LP could not be
>>>> solved, typically due to numerical problems. If you only have integer
>>>> variables then in the worst case the subtree below is solved by complete
>>>> enumeration. But you seem to be lucky: inference branching is only called
>>>> twice on the pseudo solution, so either the subtree can be pruned early or
>>>> the numerical troubles disapppear after branching.
>>>>
>>>> Maybe you can investigate from the log (increase display/verblevel) if
>>>> some of the LPs are unsolved.
>>>>
>>>> Best,
>>>> Ambros
>>>>
>>>>
>>>> Am 22.05.2018 um 02:14 schrieb Matheus Ota:
>>>>
>>>>> Hi Ambros,
>>>>>
>>>>> Thank you for replying! Yes, I have read the Constraint Handler and
>>>>> the Branching Rule tutorials. Let me give more details:
>>>>>
>>>>> - These are the parameters I chose for the Constraint Handler:
>>>>> sepapriority: 1000000
>>>>> enfopriority: 1000000
>>>>> checkpriority: 1000000
>>>>> sepafreq: 1
>>>>> propfreq: -1
>>>>> eagerfreq: 1
>>>>> maxprerounds: 0
>>>>>
>>>>> - And these are the parameters for the Branching Rule:
>>>>> priority: 200000
>>>>> maxdepth: -1
>>>>> maxbounddist: 1
>>>>>
>>>>> - the SCIP_DECL_CONSENFOLP, SCIP_DECL_CONSENFOPS and
>>>>> SCIP_DECL_CONSCHECK check if the current solution is a feasible solution
>>>>> (obeys the constraints and is integer).
>>>>> I tried to check here only if the solution obeys the constraints,
>>>>> ignoring the integrality constraint. But my problem remained: in the
>>>>> SCIP_DECL_BRANCHEXECPS method of the branching rule, the solution that gets
>>>>> there is made only of integers. So no branching is performed.
>>>>>
>>>>> - Still, I'm able to solve correctly the problem because other
>>>>> branching is performed. As shown by the output of SCIPprintStatistics():
>>>>> Branching Rules : ExecTime SetupTime BranchLP BranchExt
>>>>> BranchPS Cutoffs DomReds Cuts Conss Children
>>>>> CVRPBranchingRule: 0.00 0.00 0
>>>>> 0 0 0 0 0 0 0
>>>>> allfullstrong : 0.00 0.00 0
>>>>> 0 0 0 0 0 0 0
>>>>> cloud : 0.00 0.00 0
>>>>> 0 0 0 0 0 0 0
>>>>> distribution : 0.00 0.00 0
>>>>> 0 0 0 0 0 0 0
>>>>> fullstrong : 0.00 0.00 0
>>>>> 0 0 0 0 0 0 0
>>>>> inference : 0.00 0.00 0
>>>>> 0 2 0 0 0 0 4
>>>>> leastinf : 0.00 0.00 0
>>>>> 0 0 0 0 0 0 0
>>>>> mostinf : 0.00 0.00 0
>>>>> 0 0 0 0 0 0 0
>>>>> multaggr : 0.00 0.00 0
>>>>> 0 0 0 0 0 0 0
>>>>> nodereopt : 0.00 0.00 0
>>>>> 0 0 0 0 0 0 0
>>>>> pscost : 0.00 0.00 0
>>>>> 0 0 0 0 0 0 0
>>>>> random : 0.00 0.00 0
>>>>> 0 0 0 0 0 0 0
>>>>> relpscost : 3.06 0.00 71
>>>>> 0 0 0 100 0 0 86
>>>>>
>>>>> I'm kinda lost here. Could you share your thoughts?
>>>>>
>>>>> Thanks,
>>>>> Matheus
>>>>>
>>>>>
>>>>>
>>>>>
>>>>> 2018-05-21 16:44 GMT-03:00 Ambros Gleixner <gleixner at zib.de <mailto:
>>>>> gleixner at zib.de>>:
>>>>>
>>>>> Hi Matheus,
>>>>>
>>>>> Have you read the priority section of the "How to add constraint
>>>>> handlers?" at
>>>>>
>>>>> http://scip.zib.de/doc-5.0.1/html/CONS.php
>>>>> <http://scip.zib.de/doc-5.0.1/html/CONS.php>
>>>>>
>>>>> Chances are your CONSHDLR_ENFOPRIORITY is set to "after
>>>>> integrality". Does that help?
>>>>>
>>>>> Best,
>>>>> Ambros
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>
>>>>> Am 19.05.2018 um 21:10 schrieb Matheus Ota:
>>>>>
>>>>> Hi Again,
>>>>>
>>>>> My bad, I made a mistake in my calculations. Actually it is
>>>>> being called in a integer but infeasible solution (that breaks
>>>>> the capacity constraint). But still, from my understanding,
>>>>> branching should be done to fix the integrality constraints,
>>>>> the
>>>>> other restrictions should be fixed by the constraint handler.
>>>>>
>>>>> Thanks,
>>>>> Matheus
>>>>>
>>>>> 2018-05-19 15:17 GMT-03:00 Matheus Ota <matheusota at gmail.com
>>>>> <mailto:matheusota at gmail.com> <mailto:matheusota at gmail.com
>>>>> <mailto:matheusota at gmail.com>>>:
>>>>>
>>>>> Hello all,
>>>>>
>>>>> I'm with a problem in my Branch-and-Cut for the CVRP. I'm
>>>>> currently
>>>>> having a problem because the Branching Rule that I
>>>>> implemented is
>>>>> calling the SCIP_DECL_BRANCHEXECPS method, even though the
>>>>> currently
>>>>> solution is already the optimal one.
>>>>>
>>>>> I also implemented the SCIP_DECL_CONSENFOLP,
>>>>> SCIP_DECL_CONSENFOPS
>>>>> and SCIP_DECL_CONSCHECK methods of the Constraint Handler,
>>>>> so that
>>>>> they check if the current solution is feasible and set
>>>>> result as
>>>>> SCIP_FEASIBLE or SCIP_INFEASIBLE. Could, someone provide
>>>>> me
>>>>> some
>>>>> help in this matter?
>>>>>
>>>>> 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>
>>>>>
>>>>>
>>>>> -- Ambros Gleixner, Research Group Mathematical Optimization
>>>>> Methods at
>>>>> Zuse Institute Berlin, http://www.zib.de/gleixner
>>>>> _______________________________________________
>>>>> 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>
>>>>>
>>>>>
>>>>>
>>>> --
>>>> Ambros Gleixner, Research Group Mathematical Optimization Methods at
>>>> Zuse Institute Berlin, http://www.zib.de/gleixner
>>>>
>>>
>>>
>>>
>>> _______________________________________________
>>> Scip mailing listScip at zib.de
>>> 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/20180523/15d1c376/attachment.html>
More information about the Scip
mailing list