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