[SCIP] Branching on optimal solution
Gerald Gamrath
gamrath at zib.de
Tue May 22 14:51:21 CEST 2018
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
> <mailto: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> <mailto: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>
> <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>> <mailto: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> <mailto:Scip at zib.de
> <mailto:Scip at zib.de>>
> https://listserv.zib.de/mailman/listinfo/scip
> <https://listserv.zib.de/mailman/listinfo/scip>
> <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> <mailto:Scip at zib.de
> <mailto:Scip at zib.de>>
> https://listserv.zib.de/mailman/listinfo/scip
> <https://listserv.zib.de/mailman/listinfo/scip>
> <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
> https://listserv.zib.de/mailman/listinfo/scip
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20180522/ce35e4b3/attachment.html>
More information about the Scip
mailing list