[SCIP] constraint handler where initial linear constraints are satisfied in CONSCHECK
Ross Anderson
rander at google.com
Fri Dec 1 16:19:25 CET 2023
Thanks.
If you end up making a change (or not), I would be interested to understand.
Ross
On Thu, Nov 30, 2023 at 4:04 AM Marc Pfetsch <
pfetsch at mathematik.tu-darmstadt.de> wrote:
>
>
>
> Hi Ross,
>
> thanks for your analysis. This raises an important point. In my opinion,
> we need to sort the constraint handlers, but we need to discuss why this
> has not already happened.
>
> Summarizing, I would say that in the long run we should definitely fix
> this. In the short run your solution of creating the custom constraint
> handler last should work.
>
> W.r.t. "completely": It is only used if you want to output the complete
> reason of why a solution is not feasible. Thus, this almost never set to
> true in ordinary SCIP code, except when it is used for debugging reasons
> or when highlighting that there is a problem with a solution that has
> been read from a file.
>
> Best
>
> Marc
>
> On 29/11/2023 20:02, Ross Anderson wrote:
> > Thanks for the suggestions. I followed Marc's advice and just tried
> > debugging down from the trivial heuristic. What was actually happening
> > was that the linear constraint handler was running, it was just running
> > after my custom handler (despite my handler having a very negative
> > priority). I see the call chain:
> >
> > heurExecTrivial ->
> > SCIPtrySol ->
> > if(SCIPsolIsOriginal) { /*true for the trivial heuristic*/
> > if(*checkSolOrig
> > <
> https://source.corp.google.com/piper///depot/google3/third_party/scip/src/scip/scip_sol.c;rcl=586370334;l=93>()*)
> {
> > SCIPprimalAddSol()
> > }
> > } else { /*did not execute*/
> > SCIPprimalTrySol
> > <
> https://source.corp.google.com/piper///depot/google3/third_party/scip/src/scip/primal.c;rcl=586370334;l=1168
> >()
> > }
> >
> > The problem appears to be in checkSolOrig(). From the docs:
> >
> > /** checks solution for feasibility in original problem without adding
> > it to the solution store; to improve the
> > * performance we use the following order when checking for violations:
> > *
> > * 1. variable bounds
> > * 2. constraint handlers with positive or zero priority that don't
> > need constraints (e.g. integral constraint handler)
> > * 3. original constraints
> > * 4. constraint handlers with negative priority that don't need
> > constraints (e.g. Benders' decomposition constraint handler)
> > */
> >
> > My constraint handler needs constraints and adds a constraint, so I am
> > in bucket 3.
> >
> > In the source we see:
> >
> > /* check original constraints
> > *
> > * in general modifiable constraints can not be checked, because the
> > variables to fulfill them might be missing in
> > * the original problem; however, if the solution comes from a
> > heuristic during presolving modifiable constraints
> > * have to be checked;
> > */
> > for( c = 0; c < scip->origprob->nconss; ++c )
> > {
> > if( SCIPconsIsChecked(scip->origprob->conss[c]) &&
> > (checkmodifiable || !SCIPconsIsModifiable(scip->origprob->conss[c])) )
> > {
> > /* check solution */
> > SCIP_CALL( SCIPconsCheck(scip->origprob->conss[c], scip->set,
> sol,
> > checkintegrality, checklprows, printreason, &result) );
> >
> > if( result != SCIP_FEASIBLE )
> > {
> > *feasible = FALSE;
> >
> > if( !completely )
> > return SCIP_OKAY;
> > }
> > }
> > }
> >
> > We see in the loop that we are checking the constraints in whatever
> > order they are stored in scip->origprob->conss. From my experiments,
> > they appear to just be stored in insertion order (maybe they get sorted
> > eventually, I wasn't able to figure this out). Specifically, if I add my
> > constraint after the linear constraints instead of before, the linear
> > constraint handler runs first and catches the infeasible solutions I
> > want it to.
> >
> > Note that the behavior is different in the other branch of SCIPtrySol(),
> > where we call SCIPprimalTrySol
> > <
> https://source.corp.google.com/piper///depot/google3/third_party/scip/src/scip/primal.c;rcl=586370334;l=1168>(),
> which calls SCIPsolCheck (instead of checkSolOrig). In this function, we
> iterate over all constraint handlers once (regardless of whether or not
> they need a constraint to run), over a data structured that is sorted by
> CHECK priority (set->conshdlrs is sorted):
> >
> > /* check whether the solution fulfills all constraints */
> > for( h = 0; h < set->nconshdlrs && (*feasible || completely); ++h )
> > {
> > SCIP_CALL( SCIPconshdlrCheck(set->conshdlrs[h], blkmem, set,
> > stat, sol,
> > checkintegrality, checklprows, printreason, completely,
> > &result) );
> >
> > So this code has the behavior I had expected, that the constraints are
> > checked in order of check priority.
> >
> >
> > *Do you think this analysis is correct? And should checkSolOrig() be
> > checking the constraints in order of check priority, rather than in the
> > order of scip->origprob->conss (which appears to be insertion
> > order)?* If this is the case, I also have the easy mitigation of just
> > adding my constraint last, instead of first, if I want CONSCHECK to run
> > last.
> >
> > Further, I now understand what "completely" does, and I will still have
> > a problem in the case of completely=TRUE, as I cannot tell whether or
> > not an earlier handler has returned infeasible when I run. It looks like
> > completely is almost always false, although maybe there is some code
> > path where it can be true (hints + display/allviols=True or when
> > counting solutions), I didn't fully investigate yet. It would be nice if
> > I could provably not worry about this.
> >
> > Thanks
> > Ross
> >
> >
> >
> > On Tue, Nov 28, 2023 at 2:18 PM Kamp, Dominik
> > <Dominik.Kamp at uni-bayreuth.de <mailto:Dominik.Kamp at uni-bayreuth.de>>
> wrote:
> >
> > Hello Ross, hello Marc,
> >
> > maybe it is not related, but I would like to add that there was a
> > recent fix of a potential bug in the checking procedure, which
> > especially applies for heuristic trivial.
> >
> > Formerly, the original constraints were checked here, which could in
> > principle lead to violated original bounds since the solution is
> > constructed to satisfy the transformed bounds only. Now, the
> > transformed constraints are checked, so that the solution is
> > guaranteed to be feasible for the transformed problem before it is
> > retransformed to the original problem.
> >
> > Nevertheless, original constraints should not be violated in either
> > way, but checking out the latest bugfix release is definitely worth
> > a try.
> >
> > Best regards,
> >
> > Dominik
> >
> > > Am 28.11.2023 um 18:54 schrieb Marc Pfetsch
> > <pfetsch at mathematik.tu-darmstadt.de
> > <mailto:pfetsch at mathematik.tu-darmstadt.de>>:
> > >
> > >
> > >
> > > Hi Ross!
> > >
> > >> Before presolve begins, the trivial heuristic is generating
> > solutions that are integer but do not satisfy the linear constraints
> > (e.g. I get all variables = 1). On these invocations,
> > checklprows=true, so I guess it is my responsibility to check LP
> > feasibility?
> > >
> > > Note that this refers to the rows in the LP, which is not
> > necessarily the same as the linear constraints, since not every
> > linear constraint might be represented in the LP. This flag
> > signifies that you should not always expect that the rows are
> satisfied.
> > >
> > > > It surprised me that
> > >> this could happen, because my check priority was lower than
> > linear constraint. If I just return FEASIBLE when checklprows=true,
> > then I am not getting a final chance to check again after the linear
> > constraints have been checked.
> > >
> > > From looking at the code (SCIP 8), there are two cases:
> > >
> > > - completely = FALSE: In this case your code will only be called
> > if all other constraint handlers returned `SCIP_FEASIBLE`. Thus, you
> > can assume that linear constraints are satisfied if your code is
> > called (although the LP rows might not be satisfied if certain user
> > specified cuts have been added).
> > >
> > > - completely = TRUE: In this case all constraint handlers always
> > are called. This option is only used to output the reasons of
> > infeasibility, so it is not that relevant what you do.
> > >
> > >
> > > I do not recall whether we changed something in the process of
> > checking between SCIP 7 and 8.
> > >
> > >
> > >> The only mitigation I can come up with is to write the extra
> > code to check that the linear constraints are satisfied myself. In
> > the context of TSP, this is easy enough, as I know what my degree
> > constraints are and don't need to traverse the SCIP model.
> > >> However, the actual problem I am working on is solver
> > independent callbacks in MathOpt (part of Google's OrTools). The API
> > we expose is similar to Gurobi, there are callbacks at MIP_NODE,
> > where the solution is fractional (but meets all linear constraints)
> > and you can optionally add cuts or lazy constraints, and a second
> > callback on MIP_SOLUTION where the solution is integer and meets all
> > linear constraints from the original model. In the latter case, you
> > must add a violated lazy constraint if one exists, otherwise the
> > solution is interpreted as feasible. Given that the user gets a
> > single callback, rather than adding many small constraints as in
> > SCIP, there isn't really any performance reason not to check the
> > linear constraints for them, and this simplifies their job.
> > >> To get this API to work, it seems like I would need to iterate
> > over all the linear constraints in the model inside of CONSCHECK
> > whenever checklprows is true. I was hoping there was a better way to
> > do this, as this doesn't really seem like what I should be doing
> > (the constraint handlers don't talk to each other generally in SCIP
> > AFAIK).
> > >
> > > Yes, this would be cumbersome and it should not be necessary
> > given the information above.
> > >
> > >> Note that if I disable heuristics, then everything seems to
> > work, at least on my examples (the docs say that CONSCHECK is
> > invoked by the heuristics).
> > >
> > > Yes, indeed.
> > >
> > >
> > > What you could do is to run the code in debug mode and set a
> > break point at the SCIPtrySol() calls in heur_trivial. If you then
> > follow the code, you will probably land in
> > scip_sol.c:checkSolOrig(). It then should first check the linear
> > constraints first, which should return "SCIP_INFEASIBLE" causing the
> > process to stop.
> > >
> > > It might be that your linear constraints are not checked
> correctly.
> > >
> > > Best
> > >
> > > Marc
> > > _______________________________________________
> > > 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>
> >
> >
> > _______________________________________________
> > 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>
> >
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20231201/a412b508/attachment.html>
More information about the Scip
mailing list