Add support for NotEqualTo !=

[LebedevRI]

These are perhaps not very high on anyone's priority list,
and models can avoid needing them, but they come up,
so i wonder if these would be welcomed? (if someone contributes them)?

1. Vector Set "monotonic": @constraint(model, [i=2:length(x)], x[i] <= x[x-i]) (configurable predicate)
2. Bridge (Int) x != 0 -> c ? (x >= 1) : (x <= -1)
3. Bridge (Int) x != y -> z = x - y; z != 0
4. Bridge x != y -> (x, y) in MOI.AllDifferent
5. Bridge x >= y -> x > y and x != y (configurable predicate)

[odow]

Let me comment on each case separately.

But 1), 2), and 3) are likely a "no." 4) is a possible. I don't understand why 5) would be useful.

Vector Set "monotonic": @constraint(model, [i=2:length(x)], x[i] <= x[x-i]) (configurable predicate)

For this, we'd need to introduce a new type Monotonic <: AbstractVectorSet end, and then a bridge from Monotonoic to Nonnegatives . This is pretty straight forward. But there is a trade off to consider. Each extra set in MOI requires code, tests, documentation, and on-going maintenance. I don't know if that is worth it just so that at the the JuMP level someone can write @variable(model, x[1:4] in Monotonic().

Bridge (Int) x != 0 -> c ? (x >= 1) : (x <= -1)

This would rewrite a MOI.NotEqualSet, which we don't have. I assume you mean the constraint to imply c in {0, 1}, c --> {x >= 1} and !c --> {x <= -1}. This is do-able, but it requires quite a lot of code. We'd also need to add the operator != to JuMP.

Bridge (Int) x != y -> z = x - y; z != 0

if you did the x != 0 case, then this would automatically be handled by the SlackBridge.

Bridge x != y -> (x, y) in MOI.AllDifferent

Okay. This has merit. Instead of adding a MOI.NotEqual set, we could just leverage the existing AllDifferent, which already has a bridge to MILP. It would mean adding support for a != b --> [a, b] in MOI.AllDifferent(2) at the JuMP level.

But that's easy. Reified is a good example to follow, replacing Val{:(<-->)} with Val{:(!=)}:

https://github.com/jump-dev/JuMP.jl/blob/a55edea07f2c3bb026d89f4e7fe88ae4755a810f/src/reified.jl#L6-L31

Bridge x >= y -> x > y and x != y (configurable predicate)

Which solver is this transformation needed for?

[LebedevRI]

@odow thank you for taking a look!

Vector Set "monotonic": @constraint(model, [i=2:length(x)], x[i] <= x[x-i]) (configurable predicate)

For this, we'd need to introduce a new type Monotonic <: AbstractVectorSet end, and then a bridge from Monotonoic to Nonnegatives . This is pretty straight forward. But there is a trade off to consider. Each extra set in MOI requires code, tests, documentation, and on-going maintenance. I don't know if that is worth it just so that at the the JuMP level someone can write @variable(model, x[1:4] in Monotonic().

My main motivation is what we've just discussed in jump-dev/JuMP.jl#3651,
it results in rather more readable model print, and is somewhat easier to write.
But let's leave that for later.

<...>

Bridge (Int) x != y -> z = x - y; z != 0

if you did the x != 0 case, then this would automatically be handled by the SlackBridge.

Aha! Okay.

Bridge x != y -> (x, y) in MOI.AllDifferent

Okay. This has merit. Instead of adding a MOI.NotEqual set, we could just leverage the existing AllDifferent, which already has a bridge to MILP. It would mean adding support for a != b --> [a, b] in MOI.AllDifferent(2) at the JuMP level.

My main problem is that said bridge (CountDistinctToMILPBridge) looks scary.

MathOptInterface.jl/src/Bridges/Constraint/bridges/count_distinct.jl

Lines 29 to 30 in 873d219

	Then, we introduce new binary variables ``y_j``, which are ``1`` if a variable
	takes the value ``j`` in the optimal solution and ``0`` otherwise.

so if in x != 0, x is known to be in [-100, 100], we introduce at least ~201 variables,
and it doesn't work at all if the range is unknown?
... while 2. would just work and only require a single new variable.

So while i do agree that this general bridge
is good as a generalization, it may not optimal.

Perhaps 4. can be an intermediate solution,
with 2. being an improvement later on?

Bridge x >= y -> x > y and x != y (configurable predicate)

Which solver is this transformation needed for?

Err, i, of course, meant x > y -> x >= y and x != y :)

[LebedevRI]

So while i do agree that this general bridge
is good as a generalization, it may not optimal.

(IOW it looks to me almost as if those alldifferent/count MLIP bridges should use this 2. trick.)

[odow]

There's certainly room to have improved formulations for the ToMILP bridges. I wrote very basic reformulations for correctness and to get something working, not because it is necessarily the best reformulation.

One design consideration that I think we agree on is that we want to, as far as possible, limit the number of functions and sets in MOI and JuMP. We don't want to turn into constraint programming where there are N different ways of writing something, and the modeling language supports M different functions, but each solver supports only a very small amount.

Normally, a good rule of thumb is that we only introduce a set if a solver has native support for it.

Perhaps as a compromise, there's room for a package of JuMP reformulations. This would make the models easier to write:

julia> module JuMPReformulations

       using JuMP

       function monotonic(x::Vector{VariableRef})
           @constraint(owner_model(first(x)), x[1:end-1] .<= x[2:end])
           return
       end

       function not_equal(x::VariableRef, y::VariableRef)
           @assert is_integer(x) && is_integer(y)
           @assert owner_model(x) === owner_model(y)
           model = owner_model(x)
           z = @variable(model, z)
           @constraint(model, z --> {x >= y + 1})
           @constraint(model, !z --> {x <= y - 1})
           return
       end

       end
WARNING: replacing module JuMPReformulations.
Main.JuMPReformulations

julia> using JuMP

julia> model = Model();

julia> @variable(model, x[1:2], Int);

julia> JuMPReformulations.monotonic(x)

julia> JuMPReformulations.not_equal(x[1], x[2])

julia> print(model)
Feasibility
Subject to
 x[1] - x[2] ≤ 0
 !z --> {x[1] - x[2] ≤ -1}
 x[1] integer
 x[2] integer
 z --> {x[1] - x[2] ≥ 1}

[LebedevRI]

Yes, i very much understand being vary of adding ever more stuff to support.
I'm bringing this up because these seem to not be too "outland-ish special-cases",
that keep coming up. I'm sure i've seen ordering being mentioned at least once
on discuss, and i've personally found it to be generally useful to severely constrain
the problem space. And non-equality / strict inequality is a rather known limitation of LP,
that we can easily sidestep for integers.

Again, everyone's mileage may vary, not everything will be useful for everyone,
i'm just really hoping that these can be recognized as worthwhile having.

To summarize, let me look into the seemingly least controversial one,

Bridge x != y -> (x, y) in MOI.AllDifferent

[odow]

because these seem to not be too outland-ish special-cases

True, except that the reformulations often perform poorly. I'm hesitant to add something like != to JuMP because people will miss-use it. I can see people asking why x and y need to be integer, or why a model with != runs so much slower than ==. It's also a reason why we haven't added >, because people really, really want to use x > 0 and yet solvers cannot support that.

In some ways, forcing people to write an expansion for != forces them to think about what it is they are trying to model.

[LebedevRI]

Ack, i've actually thought/wondered about that, but in the more general sense:
now that there's generic non-linear support, is there any way to opt-out of it? :)
Not that there is a specific need, but just because.

As for performance, sure, but i can't imagine
c in {0, 1}, c --> {x >= 1} and !c --> {x <= -1} would perform that bad.

[odow]

now that there's generic non-linear support, is there any way to opt-out of it?

No

c in {0, 1}, c --> {x >= 1} and !c --> {x <= -1} would perform that bad.

The other issue is that it's very sensitive to the formulation being able to detect that x is integer:

model = Model()
@variable(model, x, Int)
@variable(model, y)
@constraint(model, x == y)
@constraint(model, x != 0)  # Works
@constraint(model, 2x != 2)  # Fails
@constraint(model, y != 0)  # Fails

[LebedevRI]

The other issue is that it's very sensitive to the formulation being able to detect that x is integer:

So we'd make it picky in so that it's operands must be [Binary] variables.

[blegat]

Whether or not we add a new set in MOI should be based on the fact that several solver supports these set natively. If only a single solver supports this set, then the solver can define it in the MOI wrapper (see for instance SCS and ECOS). If two solver share a same set then it makes sense to consider adding it in MOI. Are the sets you suggest supported by any solver ? If not, you can still make a case that it's very helpful for modeling and fits well within the existing sets and bridges in MOI (then, once it's added, maybe it will enable solvers to start supporting it)

[LebedevRI]

Are the sets you suggest supported by any solver?

I'm not aware of any supported solver supporting strict inequalities (!=, >, <),
but to be honest i haven't actually checked.

If not, you can still make a case that it's very helpful for modeling and fits well within the existing sets and bridges in MOI (then, once it's added, maybe it will enable solvers to start supporting it)

That's my reasoning, yes. This MOI.NotEqual set would have a straight-forward bridge
(to the c in {0, 1}, c --> {x >= 1} and !c --> {x <= -1} form, which is much better than what MOI.AllDifferent does),
would (probably?) allow to improve existing CountDistinctToMILPBridge bridge,
and would allow to have a straight-forward support for !=, >, < of Int/Bin decision variables.

I haven't checked, can a MOI.set take either two vectors, or a two-column matrix?
If yes, then, unlike the MOI.AllDifferent approach, we won't need to scalarize vector inequality.

To me, this seems like an obvious improvement, even if a bit controversial one.

To be most precise, i don't think strict inequalities make sense for non-MILP, only for MILP.

[mlubin]

I'm not really in favor of adding MOI sets only for the benefit of better model printing and ease of writing the model. MIP modeling is hard, and if we present an interface to users that pretends that it's easy (just pick the right set and let JuMP do the work) then we'll invite users into the bad habit of not understanding what the solver is seeing. This is super important for MIP modeling in particular, maybe less so far nonlinear. A lot of these indicator constraint formulations are technically correct but probably not most efficient as the size of the problem scales up. I'm worried that we'll get a ton of support questions along the lines of "why is my model with 1000 NotEquals constraints slow?".

Oscar's example of a library of extra helper functions makes a lot of sense IMO. Then it's very clear what's going on.

[LebedevRI]

The performance concern is valid, sure, here's some 5c from me:

This seems a bit unaligned with the current handling of sets:
if some set is not supported by some solver, then the model,
easily written by the user, will be very much not what the solver will actually use.

MathOptInterface.jl/src/Bridges/Constraint/bridges/count_distinct.jl

Lines 29 to 30 in 873d219

	Then, we introduce new binary variables ``y_j``, which are ``1`` if a variable
	takes the value ``j`` in the optimal solution and ``0`` otherwise.

If that is a problem, does it not seem like it already exists?
Should MOI error out on not-natively-supported sets?

I don't quite get why it matters where the code that is "slow"
is located, in MOI, JuMP or new jump-dev/JuMPReformulations,
as a new set, "bridge" at JuMP constraint build time, or something less fancy.

Also, efficiency of something that does not allow to solve some problem
is zero, which is always worse than that of a poor inefficient formulation.
The calculation is of course different depending on the specifics,
but again, i only brought this up because set in question is as low-level,
basic and generic of a modelling toolkit puzzle piece as you could get...

Again, just my 5c.

[mlubin]

As mentioned above, the general principle is for MOI to be an abstraction over solvers. We add sets to support constraints that are supported natively by a solver (or even better, a family of solvers). We added sets like AllDifferent and CountDistinct because they're very standard sets supported by constraint programming solvers. Yes, we support transformations between MOI sets for user convenience, and sometimes those transformations let you write problems in a way that's not the most efficient. That's the point in the trade-off curve we've chosen to balance the concerns we've been discussing.

[odow]

See also the implementation at jump-dev/JuMP.jl#3656

We added sets like AllDifferent and CountDistinct because they're very standard sets supported by constraint programming solvers.

@LebedevRI I get that NotEqual is a very natural extension of this idea. But being able to write @constraint(model, x != y) is a lot easier than @constraint(model, [x, y] in MOI.AllDifferent(2)), so users may not research exactly what is happening under the hood. As Miles says, it's a trade-off.

This seems a bit unaligned with the current handling of sets:

It's worth viewing the constraint programming sets in the context of
https://jump.dev/announcements/2022/07/12/constraint-programming/

[LebedevRI]

Okay, and if we go with "don't add Set's to MOI unless supported by supported solver",
and instead add them elsewhere, two questions:

1. would it be in jump-dev org or elsewhere? (i'm tentatively guessing it would be MathOptInterfaceExtras + JuMPExtras repos)
2. what would be the ruleset for those repos? certainly just merging every change, that was previously rejected from MOI/JuMP, into those new repos is not the path forward.

[odow]

With these things, we often ask that people start experimenting with ideas in a personal repository, e.g., LebedevRI/HelpfulMathProgrammingReformulations.jl.

what would be the ruleset for those repos?

The most useful part of it being in your own repository is that you get to decide. Do what ever you think is best. Being able to demonstrate something that works is a good way of overcoming our objections 😄. It may also turn out that you learn "these three things were good ideas, these two were bad," and then we can incorporate those lessons back into MOI. We tend to be conservative adding things to MOI/JuMP because we get locked into supporting them and ensuring backwards compatibility. You don't have these limitations in your own repo.

We've documented how and when we would consider moving this to jump-dev:
https://jump.dev/pages/governance/#transferring-repositories-to-jump-dev

(A good example is https://github.com/trulsf/UnitJuMP.jl, which may one day become official jump-dev/JuMP.jl#1350)

[odow]

This is a related post to jump-dev/JuMP.jl#3656 (comment)

We discussed this issue at length on the monthly developer call.

Thoughts:

• We understand the motivation. This is a feature request that has and will continue to be asked.
• We don't want to become a constraint programming language like MiniZinc with a very large number of predicates
• We need to draw the line somewhere, even if it is arbitrary and we have been inconsistent in the past
• Guiding principles are "do multiple solvers implement/exploit this" and "is it useful for users"
• For now, NotEqualTo is the equivalent of AllDifferent(2), so this doesn't provide any extra utility to users, and only MiniZinc.jl would support it directly.

Conclusions:

• We will not add the NotEqualTo set
• We will look at improving the AllDifferentToMILPBridge for the special case in which there are two elements.

I think the best path forward is a JuMP extension repository that contains a bunch of reformulations (at the JuMP level) for people interested in constraint programming.

[LebedevRI]

Thank you for taking a look

• We will look at improving the AllDifferentToMILPBridge for the special case in which there are two elements.

FWIW, it is not at all obvious to me why the whole expansion should not be expanded to the two-element case first,
since "clearly", the further expansion of two-element case results in much smaller/nicer MILP formulation?

• alldifferent(x[1:n]) <-> for i in 1:n for j in i+1:n alldifferent(x[i], x[j])

[odow]

That expansion results in N(N-1)/2 constraints, and we'd then have to reformulate. If we did your indicator constraint approach, that's N(N-1) indicator constraints which is pretty expensive.

The current one lowers to (N, x) in CountDistinct(), which then adds a bunch of binary variables: https://jump.dev/JuMP.jl/stable/moi/submodules/Bridges/list_of_bridges/#MathOptInterface.Bridges.Constraint.CountDistinctToMILPBridge

It isn't obvious which is more efficient in practice.

[odow]

I've opened a PR to improve the bridge reformulation: #2416, and I've marked that merging it will close this issue.

[blegat]

We don't want to become a constraint programming language like MiniZinc with a very large number of predicates

To complement, the idea of understanding Constraint Programming predicates at parsing time in JuMP macros was attempted in jump-dev/JuMP.jl#2241 and it wasn't merged. What we do in JuMP macros need to work for any field of optimization and should be quite simple and transparent. On the other hand, with the new nonlinear interface, it's getting easier to create arbitrary expression graphs in JuMP and then the solver is free to parse it as it likes. This allows meta-solvers like Convex.jl to do DCP or for a CP meta-solver to understand CP primitives. So, thanks to jump-dev/JuMP.jl#3530, you can now write @constraint(model, monotonic(x, y) := true) or @constraint(model, not_equal(x, y) := true) and a CP meta-solver could rewrite this into @constraint(model, [x, y] in Monotonic()) or @constraint(model, [x, y] in MOI.AllDifferent(2)). However, supporting @constraint(model, x != y) didn't seem appropriate. First, since it's a scalar constraints, we would reformulate it to @constraint(model, x - y in NotEqualTo(0)). And then you would loose the structure that it is two variables so [x, y] in MOI.AllDifferent(2) keeps more structure. It's always tempting to be more user-friendly but there is a trade off with being more obscure and this seemed to be on the wrong side of the trade off.