jump-dev
[Bridges] fix Constraint.ZeroOne bridge with existing bounds
Alternative to #1787. I think this is preferable as it's more correct in allowing other bounds to be set, even if it's a little slower by adding scalar affine inequalities (although these should get presolved out).
It also fits with the ethos of allowing users to move closer to the solver: if they use Mosek they can remove the bridges by declaring @variable(model, 0 <= x <= 1, Int) instead of @variable(model, x, Bin).
Closes #1787 Closes #1431
Users setting bounds on binaries should expect to get errors about bounds being set twice
No, this is something that is explicitly allowed in JuMP, and is probably more common than you think. I'm sure lots of people would write something like
@variable(model, 0 <= x[s in S] <= ub[s], Bin)
and for some s, ub will be 0.0.
I would allows solvers to throw errors if there are bounds on binary variables. Users that want their model to work with any solver shouldn't do that.
I don't like the argument that presolve could resolve this. If that was the case then why do we need VariableIndex constraints ? If the bridge is used before printing, writing to a file, dualization (after relaxation), etc..., the user will be suprised that the [0, 1] bounds were not added as bounds.
If they print a model that has been bridged, anything can happen. I think it's more surprising that some solvers would throw an error if you add a binary variable with bounds, than a binary variable's bounds being added as a constraint.
agreed with @odow, if one adds additional branching for some reason on another problem and solves the current MIP as a subproblem, updating lower or upper bounds to fix the binaries is a convenient way to do it
Why don't we just allow adding a bound when one is already set? It would be equivalent to calling set. It's also annoying for the user to keep track of whether a bound has been set or not to know whether to call add_constraint or set. As ZeroOne sets bounds, allowing to set bounds with ZeroOne is already sort of inconsistent so allowing double bounds should be fine. The whole reason for this error is that if you set an upper bound then fix it to a different value and then try to get the bound then you will get the fixed value. However, now that the constraint index equal the variable index I find tjis behaviour less shocking
Why don't we just allow adding a bound when one is already set?
Because that's now a pretty breaking change across MOI.
As ZeroOne sets bounds, allowing to set bounds with ZeroOne is already sort of inconsistent
The ZeroOne doesn't add bounds. It constraints a variable to the set {0, 1}, which is not the same as saying 0 <= x <= 1. You can clearly say something like x ∈ {0, 1} ∩ [0.5, 1].
In general, I get that we could have made different decisions. But the current problem is that @variable(model, x >= 0, Bin) in Mosek will throw an error, even though we've decided that that is perfectly valid code for every solver not using the ZeroOneBridge.
Our options are:
- Change MOI to allow multiple bounds, and break code that assumes querying the set will return you the right bound
- Change these bound constraints to linear inequalities
Surely the second is the simplest?
It wouldn't break any that currently does not error. Code that currently throws because double bounds are set will now work. Having to do
ci = MOI.ConstraintIndex{typeof(x),typeof(set)}}(x.value)
if MOI.is_valid(model, ci)
MOI.set(model, MOI.ConstraintSet(), ci, set)
else
MOI.add_constraint(model, x, set)
end
is also a complicated code for something as simple as setting a variable bound.
It breaks any code that assumes it can set and get a bound without the user modifying it. We made a pretty conscious decision to prevent multiple bounds, so I'm hesitant to change that.
Here's someone trying to add bounds on binary variables: https://discourse.julialang.org/t/xpress-julia-api-has-bug-with-fixing-variables/82895
Yes, it seems to be an important feature. I don't really like adding a SAF constraint either. The only satisfactory answer is to allow double bound.
I understand the argument that it would be breaking for code that assumes that MOI.get on the set of MOI.VariableIndex constraint will not be changed externally.
ci = MOI.add_constraint(model, x, MOI.LessThan(1.0))
# ...
MOI.get(model, x) # You expect to get MOI.LessThan(1.0), is it a bug if you get something else ?
For constraints other than MOI.VariableIndex, it would be a but that you do not get the same set. Since you own the constraint index and you have not passed it to any other code, it's not possible that another code has modified it.
However, for MOI.VariableIndex, you can do
function set_upper_bound(model, x, ub)
set = MOI.LessThan(ub)
ci = MOI.ConstraintIndex{typeof(x),typeof(set)}}(x.value)
if MOI.is_valid(model, ci)
MOI.set(model, MOI.ConstraintSet(), ci, set)
else
MOI.add_constraint(model, x, set)
end
end
So if you don't own the variable, then you cannot assume that an external piece of code didn't do this and modify your bound.
So I don't think it is breaking and any code like the above assuming that MOI.LessThan(1.0) should be returned is incorrect even for MOI v1.0.0.
The only change I'm suggesting is that MOI.add_constraint(model, x, MOI.LessThan(ub)) can now be thought as a shortcut to set_upper_bound(model, x, ub). This only changes the scenario that were previously erroring so that's not breaking for code calling this. An it's also not breaking for external code as explained above since you could already do set_upper_bound before.
I think for the short-term, this is the right bug-fix. We can have a longer discussion about whether to allow add_constraint to modify existing variable bounds.
I'd rather keep this bridge as is and wait for the right fix. Unless there is something needed a fix urgently ?
The more I think about it, the more I think this PR is the right solution. Double bounds are going to become a problem if when we delete binary constraints. Consider
model = Model()
@variable(model, x, Bin)
@variable(model, y >= -0.5, Bin)
@variable(model, 0 <= z <= 1, Bin)
# ...
unset_binary(x)
unset_binary(y)
unset_binary(z)
What are the bounds on x, y, and z?
If the bridge goes and modifies variable bounds, then it's going to have to remember the old bounds. But what if someone modifies the variable bound before calling unset_binary?
model = Model()
@variable(model, x, Bin)
# ...
set_lower_bound(model, x, 0.5)
unset_binary(x)
There's a whole bunch of complicated edge-cases you'd have to consider. It's much simpler to just add linear constraints. If the user wants to move closer to the solver, they can use @variable(model, 0 <= x <= 1, Int).
The current behavior is a bug for users of Mosek.
You are right, variable bounds are quite annoying and I don't see how we can make them work better with composability. It was also the only tests that were failing for the conic solvers we did at the ICCOPT summer school: https://github.com/blegat/ICCOPT_SummerSchool_2022/blob/main/SimpleConicADMM/test/MOI_wrapper.jl We might need to talk about variable bounds at JuMP-dev or at a dev call, I just discussed this with @joaquimg and @frapac and it's also a pain point for Knitro and Xpress wrappers.
Bounds aren't composable because they're treated specially by solvers. No solvers have support for multiple variable bounds, so adding that to MOI is difficult.
The current behavior is a bug. Bridges should produce correct reformulations, even if they aren't the most efficient. If users want to be more efficient, they can rewrite the model to be closer to the solver. That was literally part of the MOI paper.
Extra gain of salt. Historically, I think the main reason we have "variable bounds" in the first place (as opposed to just adding them as linear constraints), is because simplex-based LP solvers had a special handling of them. It's also, as @matbesancon mentioned, a great way to handle branching decisions. So mostly low-level stuff.
With the advent of presolve routines, linear constraints of the form, e.g., x >= lb, get converted internally to variable bounds anyway. That conversion is pretty fast, and keeping track of a bunch of x >= lb constraints is unlikely to be a performance sink (compared to the rest of the problem). As a user, I also find it more convenient to track the duals when I have those as linear constraints. Something we often tell our students is not to use variable bounds unless they know what they are doing (especially when we start looking at duals).
The current behavior is a bug. Bridges should produce correct reformulations, even if they aren't the most efficient. If users want to be more efficient, they can rewrite the model to be closer to the solver.
I fully support that. I am also fully supportive of not allowing multiple bound constraints. In addition to it being a breaking change, I think it would be more confusing that anything.
BTW, regarding Mosek: in their v10 release, they are departing away from VectorOfVariables-in-Cone constraints, which instead will be handled as VectorAffine-in-Cone constraints.
Just discussed this with @joaquimg and we agree. @blegat, I think you're on the loosing side. Final objections?
IIRC, the last time we talked about it, it was on the phone and the plan was to not support deletion of this bridge and to add the constraint in final_touch. In final_touch, in case there is a bound already set, we modify the bound but only in case it is tighter.
It would mean that if a user sets an upper bound of 1.5 to binary variables, then he will get 1.0 as an upper bound which I think is fine. As the constraint index of variable bounds is set to the index of the variable, no one "owns" a variable bound so no piece of code can assume that a variable bound is not modified by other part of the code.
IIRC, the last time we talked about it, it was on the phone and the plan was to not support deletion of this bridge and to add the constraint in final_touch. In final_touch, in case there is a bound already set, we modify the bound but only in case it is tighter.
I keep going back and forward on this. And I know when we talked you convinced me, but on reflection it just seems overly complicated for what is a simple solution. Just add the bounds as linear constraints. If users want more efficiency, they should use @variable(model, 0 <= x <= 1, Int) to reflect what Mosek actually supports.
With the advent of presolve routines, linear constraints of the form, e.g.,
x >= lb, get converted internally to variable bounds anyway.
You don't want to have to use a presolve to recover structure of a problem that was lost by the bridges.
If users want more efficiency, they should use
@variable(model, 0 <= x <= 1, Int)to reflect what Mosek actually supports.
Users don't want to have to write different models for different solvers.
What about I implement what I suggested, it's nonbreaking, so we release and wait to see if anyone complains ?
Users don't want to have to write different models for different solvers.
No, but if they use a particular solver and want better efficiency they do.
I think we need @mlubin to weigh in here.
You don't want to have to use a presolve to recover structure of a problem that was lost by the bridges.
I don't put any weight on this argument because literally every serious MIP solver will detect this structure in presolve. I would be more concerned about bridges leaving a messy model for continuous solvers that tend to not have presolve. Supposing we don't care about this point, are there additional arguments against @odow's fix?
I would be more concerned about bridges leaving a messy model for continuous solvers that tend to not have presolve
I think we do care about this issue. On the other hand, there is no issue with the fix I mentioned in https://github.com/jump-dev/MathOptInterface.jl/pull/1879#issuecomment-1282312680 so why not go for the fix that is nonbreaking and without issue instead of the breaking one with known issues ?
I think we do care about this issue.
Who would be negatively impacted by having the 0/1 bounds written as linear constraints?
On the other hand, there is no issue with the fix I mentioned in https://github.com/jump-dev/MathOptInterface.jl/pull/1879#issuecomment-1282312680 so why not go for the fix that is nonbreaking and without issue instead of the breaking one with known issues ?
Not supporting deletion is one issue with that proposed solution.
What's breaking about this PR?
Who would be negatively impacted by having the 0/1 bounds written as linear constraints?
This is destroying structure of a model without knowing whether the underlying model handles variable bounds differently. Continuous solver is an example as you mention but I am also hoping that the design of MOI would allow solver to more freely define their interface and not have to fit to either MIP, conic of NL families.
Not supporting deletion is one issue with that proposed solution.
From JuMP, you have Cache{Bridge{Solver}}. If the bridge does not support deletion, it will empty the optimizer and it will be copied again from the cache at optimize! so the user won't see the difference. Bridges support deletion/modification/getters etc... but it's not so important since the cache supports all that efficiently.
What's breaking about this PR?
We change the formulation of an existing bridge.
What's breaking about this PR?
We change the formulation of an existing bridge.
The current bridge is broken. This is a bug-fix. And it doesn't change user-visible behavior. We should be able to refactor bridge implementations without it being considered breaking.
The breaking part is not important so I won't argue with that. The reformulation is destroying structure, that is my issue with it. Bridges only destroy structure when it is not supported by the solver.
Removing support for deletion is really not an issue, the implementation of MOI modifications for bridges is really not mandatory. It usually require being able to get ConstraintFunction etc... so it might fail and in case it does not, it is usually quite slow so having the CachingOptimizer empty the optimizer and copy it again is usually the best course of action. Support for deletion would be possible to implement if we implement notification for bound changes in the bridges but I don't think it's needed.
Who would be negatively impacted by having the 0/1 bounds written as linear constraints?
This is destroying structure of a model without knowing whether the underlying model handles variable bounds differently. Continuous solver is an example as you mention but I am also hoping that the design of MOI would allow solver to more freely define their interface and not have to fit to either MIP, conic of NL families.
The reformulation is destroying structure, that is my issue with it. Bridges only destroy structure when it is not supported by the solver.
By MIP solvers I loosely mean solvers that support integer variables. They can also support conic or NL constraints. At this level of maturity, presolve transformations are basically part of the contract with users of these solvers. There's no structure being destroyed because the solver recovers the same model at the end of presolve. You haven't given an example of who would be negatively impacted by this change.
I don't know the internal of all solvers at the moment (even less in the future). Maybe Juniper ? It's a Branch & Bound solver so it should be treating bounds differently and I don't know whether it has a presolve. Maybe Alpine ? It's also doing spacial branch and bound and I don't know whether it recovers these bounds in a presolve. For teaching purpose, one could write a simple branch and bound solver just supporting integer variables and it would be quite annoying that binary variables don't get bridged into variable bounds. You don't want to have to do a presolve just for a simple solver like that.
About the deletion of the bridge. Let me add that I don't think we have many bridges supporting all operations. The bridging interface can be decomposed in three:
- The part that is needed to bridge a model (
bridge_constraint,supports_....,added_...), this is mandatory for all bridges - The part that is necessary for results of optimizer (
ConstraintDual,ConstraintPrimalStart,ConstraintPrimal), this is optionnal. For instance, bridges that are usually used with MIP usually don't implementConstraintDualalthough it is well defined (you just multiply by the adjoint of the transformation). SettingConstraintDualStartis sometimes not implemented because it requires multiplying by the inverse of the adjoint so if the adjoint is not invertible, it is sometimes unclear what to do. - The part that would be used to query the model or modify it, e.g.,
delete,modify,getConstraintFunction. This part was never requested by any user and usually, you mostly implement the part that are easy to do, e.g.,deleteorgetConstraintSet. You don't want to affect the design of your bridge in any way in order to make these parts more efficient or easier to write (like caching the constraint function, see https://github.com/jump-dev/MathOptInterface.jl/pull/1961#discussion_r928368252) because they will never be used as there is aCachingOptimizerdoing the job. And in case it is used, it will be slow so it's actually best to just drop the model. Bridges are optimized forcopy_toand modification/getters are expected to be slow and not fully implemented. Remember we used to have a cache in theLazyBridgeOptimizerbut we figured out it was there just to make it easier to pass the MOI tests so we removed it since JuMP uses another cache anyway.
For teaching purpose, one could write a simple branch and bound solver just supporting integer variables and it would be quite annoying that binary variables don't get bridged into variable bounds. You don't want to have to do a presolve just for a simple solver like that.
If it's for teaching purposes, wouldn't you start off with supporting only binary variables, not integer variables? It doesn't matter if we go out of our way to generate a clean model in this case. Solvers that handle integers will still need to have presolve of some form because users write models with bounds disguised as linear constraints all the time.
Juniper and Alpine both support the ZeroOne set.
We're talking about the case of a solver that:
- Supports integer but not binary variables
- Does not have the most basic presolve
- Someone might want to use
IMO we should prioritize keeping the bridge simple over catering to this essentially empty set.