[SCIP] constraint handler where initial linear constraints are satisfied in CONSCHECK
Marc Pfetsch
pfetsch at mathematik.tu-darmstadt.de
Thu Nov 30 10:04:14 CET 2023
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>
>
More information about the Scip
mailing list