[SCIP] Branching on optimal solution
Matheus Ota
matheusota at gmail.com
Tue May 22 14:16:00 CEST 2018
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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20180522/2713c459/attachment.html>
More information about the Scip
mailing list