[SCIP] constraint handler where initial linear constraints are satisfied in CONSCHECK

[Ross Anderson]

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>
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>:
> >
> >
> >
> > 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
> > https://listserv.zib.de/mailman/listinfo/scip
>
>
> _______________________________________________
> 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/20231129/94a72c42/attachment.html>