MOI callbacks

[matbesancon]

Now that callbacks have been shipped in MOI, they can be implemented with the constraint handler system. A good example is GLPK or CPLEX: https://github.com/JuliaOpt/CPLEX.jl/blob/master/src/MOI/MOI_callbacks.jl

[rschwarz]

True. Since SCIP constraint handlers need to implement 3-4 different callbacks (see comment in #94), there is not a faithful representation of them as a single lazy constraint callback.

One approximation would be to

• always call the lazy constraint callback (user defined) for any SCIP callback,
• use the generated constraint only in the enforce callbacks,
• implement check by counting the generated constraints (none, or more),
• implement lock by adding locks for all variables in both directions.

This is what we did in MPB/CSIP, but it's somewhat pessimistic (too many variable locks) and maybe confusing (check callback is called often, but generated cuts never added to problem).

[matbesancon]

From what I see from the issue, the only point of ambiguity is on a lock strategy? As I understand them, the only variables for which lock is true would be the ones used either in the constraint or in the condition to check the constraint?

[rschwarz]

Yes, the constraint handler must add locks to all variables where changing the assignment (e.g. rounding) to a lower or higher value might violate the constraint.

EDIT: So, it's safe to always lock all variables in both directions.

[matbesancon]

To come back to this issue, three possibilities I see:

• Offer a vanilla type of callback (with all variables of the model)
• use something like IRTools to analyze the callback function when it is passed and extract the variables it touches
• when implementing the callback set function, add a last argument variables with default to allvariables(optimizer), so that users can tune this default.

[rschwarz]

I like the last option best, because it's still convenient for the user, but they are aware that there is a decision to be made.

[matbesancon]

I'm not sure where option 2 would be located in terms of compromises and advantages, do you know of anyone who has used it for similar use cases?
Pinging @odow to know if some other options have been considered for other solvers

[rschwarz]

I have not used IRTools knowingly. Analyzing the user code sounds a bit shaky to me, as well as difficult to implement.

[odow]

If SCIP doesn't have a nice way of meeting MOI.LazyConstraintCallback, don't implement it. Just provide solver-dependent callbacks instead. If that means users writing 3 different callbacks, so be it. Callbacks are nasty and not solver-independent, and SCIP has a very different structure compared to the other solvers.

[matbesancon]

So @rschwarz the way forward will be to implement the lazy callbacks based on https://github.com/SCIP-Interfaces/SCIP.jl/blob/master/src/conshdlr.jl but at the MOI level? The current functions are fairly low-level for MOI users

[rschwarz]

To be honest, I don't have a good idea about how to improve the usability here.

I feel like users should know and understand the SCIP principles, in order to achieve correctness without surprises. Given that, any kind of syntactic sugar or sensible defaults might not add a lot of value. In that sense, it's good enough for my own use case.

But it might mislead users to think that the callbacks work the "same way" as with other solvers. So, if there will be any compatibility layer, it should be generous with warning messages.

[jovarga]

What about the user-cut callback? It should be possible to support it via SCIP separators. And as there is only a single mandatory callback for separators, it is not misleading for users. Or am I missing something there?

[rschwarz]

Yes, I believe that user-cut callbacks should not lead to interface mismatch. Similary, the primal heuristic callbacks should also be relatively straight-forward (with sensible defaults for the timing).

[jovarga]

Is there any chance, that this will be implemented within the next 2-3 months? I would need it for my current project.

[rschwarz]

I'm not going to volunteer for it, but I can review pull requests and answer questions.

[jovarga]

Ok. I will try then.

Thank you!

[jovarga]

I finished implementing the user-cut callbacks, however I have difficulties with testing. So two questions about that:

1. Is there an easy way to force SCIP to call a separator? At the moment I use a MIP with two variables and disable some features of SCIP (presolving and some heuristics). But I do not consider that a good test, as new features of SCIP may break it.
2. How to check, that the cuts have been added to the LP? What I tried so far: Give SCIP a MIP with two optimal solutions, cut away one of these solutions in the cutcallback and check, that the other solution is selected by SCIP. However the added cut does not seem to make a difference. Note that cutting away a solution in that case is OK for SCIP, as stated in https://scipopt.org/doc/html/FAQ.php#conshdlrvsseparator:

The set of feasible integral vectors does not change if a cutting plane is removed. You can, however, relax this condition slightly and add cutting planes that do cut off feasible solutions, as long as at least one of the optimal solutions remains feasible.

[rschwarz]

Re 1: I'm not sure about forcing, but according to the docs you should be able to set the SEPA_FREQ and SEPA_PRIORITY in a way that your separator is called at every node and as the first separator.

Re 2: I can think of two ways:

• Add cuts that actually do cut off solutions and verify the solution value. This would be against the "contract" of the plugin type, but if your separator is called and the cut is added, then this fact would be evident in the returned solution.
• You can also use a (global?) variable that counts how often your separator is called. You could then check that it was called at least once. This is also what I do to test the constraint handlers (see counter and test).

Feel free to open a PR, even if it's not yet ready to be merged, then we can discuss details there.

[matbesancon]

@rschwarz should this be closed with #179?

[rschwarz]

I think it makes sense to close this, even though other MOI callbacks are not (yet) supported. We can add new issues or PRs that are more specific, as needed.