Jump.jl: Allow `@constraint` without relational operator?

[dourouc05]

Thinking longer term: why is @constraint limited to using relational operators (<=, >=, and ==)? Getting rid of this limitation would be very useful if adding constraint programming into JuMP (I have plans for that, but not quite soon): you assert that something is true (like alldifferent).

Closer to present, I'm working on https://github.com/dourouc05/MOModelingExtensions.jl, to allow beginners to write some expressions more easily (with brute-force formulations that work everywhere, even though they could be simplified in most cases — but I'm not analysing the formulation as a whole to improve it). It would be nice to write something like @constraint(m, any([x, y, z])) instead of @constraint(m, any([x, y, z]) == true).

So, the functionality as I imagine it: allow JuMP to parse things like @constraint(m, any([x, y, z])), and then let extensions do the rest of the work.

(I prefer to bring this issue sooner than later, in case this would entail design decisions that would require breaking changes and thus would have to wait for JuMP 2.0…)

[mlubin]

The @constraint macro is due for a rewrite, although it's currently not on the 1.0 roadmap. That doesn't mean it won't happen before 1.0, but it means that none of the core developers have committed to do it.

My first question for this is, why are macros needed? The two reasons that we have macros are (1) for performance, because naive summation of affine expressions using operator overloading is O(n^2), while we can rewrite sums to be O(n) using macros, and (2) a macro gives us a syntactic context in which we can change the definition of the relational operators. In regular Julia code, the operators return bools, while inside the macros they're reinterpreted as mathematical constraints. It's not clear that either of these two motivations still holds for the examples you mentioned.

Could you do add_constraint(m, any([x, y, z])) or add_alldifferent(m, [x, y, z])? What kind of object does any([x, y, z]) return?

[dourouc05]

Indeed, for this kind of constraint, the usual rationale behind macros is not so relevant: usually, just "raw" variables are passed as arguments, not really expressions (for a rare need, I suppose forcing users to use @expression is not such a big deal). Also, there is no need for macros for these expressions to be considered different than the usual boolean operators: in my implementation, even outside macros, any([x, y, z]) directly returns a new variable, not a boolean.

Currently, any just returns a VariableRef, mostly because it works more or less out of the box, without using too much of JuMP's internals. I could use add_constraint for now, but this would not really provide better syntax that @constraint(m, sth == true), due to using a different name (add_constraint vs. @constraint), from a user perspective. This is less of an issue for constraint programming (add_alldifferent), as it is a completely different modelling paradigm.

For now, I was thinking of a new type of variable, that could be called DefaultTrueVariableRef (horrible name that should indicate that JuMP should interpret a constraint with just this variable as variable == true). @constraint would not complain if it is given this type of lhs and no relational operator nor rhs (in order to minimise the risk of error: @constraint(m, x + y) makes very little sense as such, unlike boolean operators, for instance).

[mlubin]

in my implementation, even outside macros, any([x, y, z]) directly returns a new variable, not a boolean.

This design is problematic for a couple reasons:

1. This definition of any is not consistent with Base.any, so it should have a different name.
2. The code is fragile to the type of the array. Users will not understand why any(Any[x,y,z]) does not work, and the error message will not be helpful.

[dourouc05]

This is mostly a prototype, with its (many) flaws :)! I first wanted to only allow this syntax within the macro call, but I did not see a way to do it.

Here is what I've converged to for now: for non relational constraints, in _constraint_macro, rewrite x.args such that x.args[1] indicates the type of constraint and the rest of the vector the arguments; add in MOI a vector constraint (like Or, And, AllDifferent). This could easily generalise to other global constraints; some of them could be translated into MIP models transparently using bridges (at least, that's my interpretation of them), possibly using information about the model (maximising a minimum is convex, you just need a bunch of constraints, but no binary variable).

[dourouc05]

I went on to make a pre-prototype so that @constraint can handle CP-style constraints: https://github.com/dourouc05/JuMP.jl/tree/dourouc05-constraint-macro. (First time I'm writing macro code, so I guess one could do much better, such as the push.)

The main feature is to allow something like this:

m = Model()
@variable(m, x, Int)
@variable(m, y, Int)
@constraint(m, alldifferent(x, y))

To implement this constraint, a JuMP extension should provide an implementation of build_non_relational_constraint(_error::Function, head::Val{:alldifferent}, args::VariableRef...). In CP, most arguments would just be plain variable references, not really expressions, but nothing forbids defining build_non_relational_constraint(_error::Function, head::Val{:alldifferent}, args...).

The next step would be to implement a reification operator :=, different from ==: it's not an equality constraint, it's defining the value of a binary variable (and just binary). The only allowed used would be x := constraint(anything other than x). For instance, x := y | z or x := alldifferent(y, z). The meaning would be: x equal to 1 if the constraint is satisfied, 0 otherwise (usual definition of reification). It would be used to implement the binary operators I was speaking about at the beginning of this issue.

Comments welcome!

[rschwarz]

Couldn't you already define an AllDifferent() set in MOI and then do this in JuMP:

@variable(m, x, Int)
@variable(m, y, Int)
@constraint(m, c, [x,y] in AllDifferent())

just like is done with SecondOrderCone etc.?

This is not mean to discourage the discussion here, but just provide something that works now.

EDIT: See example from the docs.

[dourouc05]

I don't see why this should not work. However, the interface is not as nice as it should be for CP users, that's the main point. Also, the discussion started with Boolean expressions, for which this solution would not really make sense (or with a quite complicated interface).