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