[SCIP] Branching on optimal solution
Matheus Ota
matheusota at gmail.com
Tue May 22 20:49:18 CEST 2018
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/20180522/2ac303fc/attachment.html>
More information about the Scip
mailing list