<div dir="ltr"><div dir="ltr">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:<br></div><div dir="ltr"><div><br></div><div><font face="monospace">heurExecTrivial -></font></div><div><font face="monospace">SCIPtrySol -></font></div><div><font face="monospace"> if(SCIPsolIsOriginal) { /*true for the trivial heuristic*/ </font></div><div><font face="monospace"> if(<b><a href="https://source.corp.google.com/piper///depot/google3/third_party/scip/src/scip/scip_sol.c;rcl=586370334;l=93" style="font-size:medium;margin:0px;padding:0px;box-sizing:border-box;color:inherit;text-decoration-line:none;white-space:pre-wrap" target="_blank">checkSolOrig</a>()</b>) { </font></div><div><font face="monospace"> SCIPprimalAddSol()</font></div><div><font face="monospace"> } </font></div><div><font face="monospace"> } else { /*did not execute*/</font></div><div><font face="monospace"> <a href="https://source.corp.google.com/piper///depot/google3/third_party/scip/src/scip/primal.c;rcl=586370334;l=1168" style="font-size:medium;margin:0px;padding:0px;box-sizing:border-box;color:inherit;text-decoration-line:none;white-space:pre-wrap" target="_blank">SCIPprimalTrySol</a>()</font></div><div><font face="monospace"> }</font></div><div><br></div><div>The problem appears to be in checkSolOrig(). From the docs:</div><div><br></div><div><font face="monospace">/** checks solution for feasibility in original problem without adding 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 need constraints (e.g. integral constraint handler)<br> * 3. original constraints<br> * 4. constraint handlers with negative priority that don't need constraints (e.g. Benders' decomposition constraint handler)<br> */</font><br></div><div><br></div><div>My constraint handler needs constraints and adds a constraint, so I am in bucket 3.</div><div><br></div><div>In the source we see:</div><div><br></div><div><font face="monospace"> /* check original constraints<br> *<br> * in general modifiable constraints can not be checked, because the variables to fulfill them might be missing in<br> * the original problem; however, if the solution comes from a 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]) && (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> }</font><br></div><div><br></div><div>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.</div><div><br></div><div>Note that the behavior is different in the other branch of SCIPtrySol(), where we call <a href="https://source.corp.google.com/piper///depot/google3/third_party/scip/src/scip/primal.c;rcl=586370334;l=1168" style="font-size:medium;color:inherit;margin:0px;padding:0px;box-sizing:border-box;text-decoration-line:none;font-family:monospace;white-space:pre-wrap" target="_blank">SCIPprimalTrySol</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):</div><div><br></div><div><font face="monospace"> /* 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, stat, sol,<br> checkintegrality, checklprows, printreason, completely, &result) );</font><br></div><div><br></div><div>So this code has the behavior I had expected, that the constraints are checked in order of check priority.</div><div><br></div><div><br></div><div><b>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)?</b> 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.</div><div><br></div><div>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.</div><div><br></div><div>Thanks</div><div>Ross</div><div><br></div><div><br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Tue, Nov 28, 2023 at 2:18 PM Kamp, Dominik <<a href="mailto:Dominik.Kamp@uni-bayreuth.de" target="_blank">Dominik.Kamp@uni-bayreuth.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">Hello Ross, hello Marc,<br>
<br>
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.<br>
<br>
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.<br>
<br>
Nevertheless, original constraints should not be violated in either way, but checking out the latest bugfix release is definitely worth a try.<br>
<br>
Best regards,<br>
<br>
Dominik<br>
<br>
> Am 28.11.2023 um 18:54 schrieb Marc Pfetsch <<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 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?<br>
> <br>
> 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.<br>
> <br>
> > It surprised me that<br>
>> 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.<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 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).<br>
> <br>
> - 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.<br>
> <br>
> <br>
> I do not recall whether we changed something in the process of checking between SCIP 7 and 8.<br>
> <br>
> <br>
>> 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.<br>
>> 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.<br>
>> 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).<br>
> <br>
> Yes, this would be cumbersome and it should not be necessary given the information above.<br>
> <br>
>> 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).<br>
> <br>
> Yes, indeed.<br>
> <br>
> <br>
> 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.<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><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><br>
<a href="https://listserv.zib.de/mailman/listinfo/scip" rel="noreferrer" target="_blank">https://listserv.zib.de/mailman/listinfo/scip</a><br>
</blockquote></div></div>