Expose callbacks for various SCIP plugin types.

[rschwarz]

Since SCIP support for plugins (callbacks) is more general that what is available in other MIP solvers, it makes sense to offer a thin layer around the SCIP style of them, for example:

• constraint handlers (lazy constraints)
• heuristics (based on LP solutions, but also from scratch type heuristics, or improving heuristics)
• relaxations (instead of, or in addition to LP)
• branching rules
• node selection rules

If/when a callback interface is established for MOI, this layer could be used then.

[rschwarz]

See also discussion in https://github.com/JuliaOpt/CPLEX.jl/pull/207 for a candidate interface that could be used as a template.

[rschwarz]

My personal motivation would be to expose constraint handler plugins first (in full generality) with a thin convenience wrapper (à la lazy constraint callback), in the coming weeks.

Then heuristics, and (much?) later the other plugin types.

[mlubin]

I'd like to brainstorm how to expose constraint handler plugins in full generality without SCIP needing to depend on JuMP. Could you give a brief summary of what callbacks are needed to implement a constraint handler? I remember there are multiple functions to implement.

[rschwarz]

For constraint handlers, there are 3-4 required callbacks:

• check: given a solution candidate, check constraint violation and return boolean
• enfo(rce): given a solution candidate, iff constraint is violated, do something about it (e.g. add a constraint, create branches).
• lock: for each variable, say whether rounding up or down could violate this constraint. This could be set to "all true", conservatively, breaking some heuristics/preprocessing.

There are two versions of enfo, one for LP solutions, and one for pseudo-solutions (which have some different, heuristic origin and might not satisfy the LP relaxation), but it is common (I think) to use one implementation for both of these.

In addition, there are lots of optional callbacks: Some of these are for data bookkeeping (memory mgmt, copies of data, transformation during presolve etc), others algorithmic (sepa for cut separation, prop for bounds propagation).

Looking at the documentation, I'm now hesitant with my previous claim of "full generality" ;-) My idea was to provide an abstract type for constraint handlers and have users implement these callbacks via multiple dispatch, providing some empty default implementations. Because of the wide scope, I guess that users will have to use some of the ccall wrappers directly, but there should be convenient shortcuts for common operations, such as querying the current LP relaxation values etc.

EDIT: I have not thought about any JuMP interaction, actually. I only skimmed over the discussions about generic callbacks in GLPK, CPLEX etc., saw that it was possible and decided to look up the code as needed.

[mlubin]

If I understand correctly, after you register a constraint handler for X-type constraints, you can add arbitrarily many X-type constraints, right?

Do we want to support this, or should we blur the abstraction and say that if you want to enforce X-type constraints, the one constraint handler has to know all the data (which is more like how lazy constraints work)?

For the former, we could model X-type constraints through a new MOI function. So you could register a constraint handler and then independently add X-type constraints.

Just throwing ideas out. I'd say we should first focus on a clean MOI implementation and then the JuMP interaction should follow from that.

[rschwarz]

If I understand correctly, after you register a constraint handler for X-type constraints, you can add arbitrarily many X-type constraints, right?

That is correct, although it is also optional.

So, for example, with a constraint handler for subtour elimination, it might only make sense to have a single constraint in the problem. I think there is a boolean flag like needs_constraint to make such a singleton constraint.

I think it makes sense to support it. That way, the same kind of constraint could be applied, say, to different blocks of a model. Also, it might even make the interface to JuMP easier, if a user has to hand some data explicitly into the constraint, such as a list of variables.

Rather than adding an MOI function, it could also be an MOI set, right? That's what I did for the abspower constraint in SCIP.jl.

[rschwarz]

From the docs:

CONSHDLR_NEEDSCONS: indicates whether the constraint handler should be skipped, if no constraints are available. Usually, a constraint handler is only executed if there are constraints of its corresponding class in the model. For those constraint handlers, the NEEDSCONS flag should be set to TRUE. However, some constraint handlers must be called without having a constraint of the class in the model, because the constraint is only implicitly available. For example, the integrality constraint handler has the NEEDSCONS flag set to FALSE, because there is no explicit integrality constraint in the model. The integrality conditions are attached to the variables, and the integrality constraint handler has to check all variables that are marked to be integer for integral values.

Maybe my example of subtour elimination does not fit the recommended use. In that case, would suggest to have an explicit constraint, in even in the case of subtour elimination.

So far, when adding new features, there have been three layers, typically:

• the Clang-generated wrapper on top of the ccall, with identical signature, but as a Julia function.
• a thin convenience wrapper for ManagedSCIP to take in Julia data (say, an Array{Float64}, rather than Ptr{Float64}) together with registering the Ptr{SCIP_VAR} and Ptr{SCIP_CONS}.
• the implementation of the MOI interface methods.

In the case of constraint handlers, it might also make sense to have a more-or-less complete interface at the ManagedSCIP level, using dispatch to save the user from handling function pointers. On top of that, a simplified and opinionated wrapper for MOI.

[matbesancon]

To keep track of the progress here, most of the announced ones are done, what would be missing is a more MOI-like way of doing it with abstract submittables or at least optimizer attributes

done:

• constraint handlers (lazy constraints)
• separator
• cut selector
• heuristics (based on LP solutions, but also from scratch type heuristics, or improving heuristics)
• branching rules

to do:

• relaxations need some work and docs on the SCIP side
• node selection rules, less urgent as less demanded

[matbesancon]

edited the status above, I don't think there is much left to do except improving the constraint handler to make it easier to access