[SCIP] Branching on optimal solution
Ambros Gleixner
gleixner at zib.de
Tue May 22 07:51:12 CEST 2018
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
More information about the Scip
mailing list