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

[Ross Anderson]

Hi,

I would like to write a constraint handler (for the purpose of adding cuts
and/or lazy constraints) where I assume the constraints initially included
in the model are all satisfied whenever my handler runs. For example, if my
problem were TSP, I want to be able to assume (at least on integer
solutions) that the graph of connected cities is a degree two graph, as
this lets me use more efficient data structures to check for sub-cycles.

Following the advice here:

https://stackoverflow.com/questions/72921074/can-i-set-the-scip-constraint-handler-to-work-only-after-a-feasible-solution-is

I set the priority of check, enforce, and separate to -9999998, so my
handler would always run last. For most of the handler methods, (e.g.
CONSENOLP, CONSSEPALP, CONSSEPASOL) this seems to work, but I am having
problems with CONSCHECK.

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? 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.

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).

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).

I am running SCIP 7.0.1 (I haven't tried with 8 yet, but I can accept a
solution for SCIP 8 only). I don't have a minimal example that is easy for
you to run (I am programming against or-tools). But the issues I am
describing can be observed on trivial problems as well. For example, on the
problem:

max 3x + 2y + z
s.t.   x + y + z <= 2
       x, y, z Binary
       Custom constraint generating: x + y <= 1

We see in the CONSCHECK called on (1, 1, 1) with checklprows=true before
presolve runs (from the trivial heuristic), violating the constraint x + y
+ z  <= 2.

In a slightly more complicated example:

max x + 2y - z
s.t.   x + y + z >= 1
       x, y, z Binary
       Custom constraint generating: x + y <= 1

I tried to just return FEASIBLE whenever checklprows=true, to see if I
would get another chance to check my custom constraint once the linear
constraints were checked. You can see in the logs that (1, 1, 1) is
accepted as a feasible solution before presolve begins (we say feasible,
and it satisfies the only linear constraint).

To summarize, is there some way CONSCHECK to run only after the linear
constraints have been checked, or to easily simulate this behavior?

Thanks (and sorry for a long question).

Ross
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20231127/778986c5/attachment.html>