Why is Bridges.Variable.ZerosBridge needed?

[odow]

When a VectorOfVariables-in-Zeros constraint gets added, for example:

MathOptInterface.jl/src/Test/test_conic.jl

Lines 298 to 299 in e9b1f4a

	if use_VectorOfVariables
	vs = MOI.add_constraint(model, vov, MOI.Zeros(1))

It may get bridged by

MathOptInterface.jl/src/Bridges/Variable/zeros.jl

Lines 1 to 17 in e9b1f4a

	"""
	ZerosBridge{T} <: Bridges.Variable.AbstractBridge
	Transforms constrained variables in [`MathOptInterface.Zeros`](@ref) to zeros,
	which ends up creating no variables in the underlying model.
	The bridged variables are therefore similar to parameters with zero values.
	Parameters with non-zero value can be created with constrained variables in
	[`MOI.EqualTo`](@ref) by combining a [`VectorizeBridge`](@ref) and this bridge.
	The functions cannot be unbridged, given a function, we cannot determine, if
	the bridged variables were used.
	The dual values cannot be determined by the bridge but they can be determined
	by the bridged optimizer using [`MathOptInterface.Utilities.get_fallback`](@ref)
	if a `CachingOptimizer` is used (since `ConstraintFunction` cannot be got
	as functions cannot be unbridged).
	"""

The lack of dual variables causes problems in ECOS and Clp:

• https://github.com/jump-dev/Clp.jl/runs/5369296666?check_suite_focus=true
• Implement MOI.default_cache ECOS.jl#137 (comment)

The solution is just to remove the bridge. In what cases is it actually useful? I get that it can make some formulations simpler, but which ones? Why not just add the extra variables?

[odow]

They were added here: #817 with further discussion here: #759. But no motivation for adding it that I can find.

[blegat]

It makes the formulation simpler. For CSDP, otherwise, it would need to add a free variables, bridged into 2 variables and then add a linear constraint. It makes sense to disable it when running the MOI.Test but in practice it is useful.

[odow]

It makes the formulation simpler

Which formulation?

[odow]

x in {0} becomes x_1, x_2 >= 0, x_1 - x_2 = 0, substitute x_1 - x_2 for x?

How common is it to write x in {0} for CSDP?

If it's okay for most solvers to remove, why not make it opt-in for CSDP?

[blegat]

The reformulation is always what the user would expect. Without this bridge, the problem would silently be bridged to a non-optimal formulation, I don't like that. The bridges that are currently opt-out leads to UnsupportedConstraint when they are not used, no silent misbehavior. We never had any complaint. The tests are edge cases and the error produced is quite user friendly so I don't see the issue.

[odow]

the problem

Again. Which problem?

[blegat]

Again. Which problem?

I mean the model.

Consider the addition of a variable constrained on creation to be in EqualTo. That's the common use case.

1. If a solver supports VariableIndex-in-EqualTo, no bridge should be used.
2. If a solver supports VariableIndex-in-Interval or VariableIndex-in-LessThan & GreaterThan, then it should be bridged to that.
3. If a solver does not support these, then eliminating the variable and substituting it to the constant would result in the smaller formulation so it's sensible to do that.

We could check if 2. indeed holds. Otherwise, we should check if we don't need to introduce bridge costs to make this happen but if 2. holds I don't see any issue.
If users complain of not getting duals for solvers in the case 3. (but we haven't had such complain yet), they should probably not create equality constraint with such solvers and use ParametricOptInterface or ParameterJuMP. Implementing duals for ZerosBridge would be equivalent to implementing ParametricOptInterface inside the bridge optimizer. We could incorporate it but I don't know if we want to go that route.
I'd rather make sure we always generate the smaller formulation by default. If they user want to use fixed variables with solvers in the case 3., they should manually decide their preferred route:

1. Keep smallest formulation: Use ParametricOptInterface
2. User larger formulation: remove_bridge(..., Bridges.Variable.ZerosBridge

I don't like the idea of using a larger formulation by default.

[odow]

I mean the model

I meant a mathematical formulation of an optimization problem in which this bridge is useful.

I don't see what this bridge has to do with x in EqualTo. It would get bridged to ScalarAffine-in-Zeros.

Are people really writing models with x in {0}?

Edit: I think we need to talk over the phone about this.

[odow]

Okay, for some reason which I don't fully understand, using an outer caching optimizer changes the bridges that are applied:

julia> using ECOS

julia> const MOI = ECOS.MOI
MathOptInterface

julia> model = MOI.instantiate(ECOS.Optimizer; with_bridge_type = Float64)
MOIB.LazyBridgeOptimizer{MOIU.CachingOptimizer{ECOS.Optimizer, MOIU.UniversalFallback{MOIU.Model{Float64}}}}
with 0 variable bridges
with 0 constraint bridges
with 0 objective bridges
with inner model MOIU.CachingOptimizer{ECOS.Optimizer, MOIU.UniversalFallback{MOIU.Model{Float64}}}
  in state EMPTY_OPTIMIZER
  in mode AUTOMATIC
  with model cache MOIU.UniversalFallback{MOIU.Model{Float64}}
    fallback for MOIU.Model{Float64}
  with optimizer ECOS.Optimizer

julia> x = MOI.add_variable(model)
MathOptInterface.VariableIndex(1)

julia> c = MOI.add_constraint(model, x, MOI.EqualTo(1.0))
MathOptInterface.ConstraintIndex{MathOptInterface.VariableIndex, MathOptInterface.EqualTo{Float64}}(1)

julia> MOI.optimize!(model)

ECOS 2.0.8 - (C) embotech GmbH, Zurich Switzerland, 2012-15. Web: www.embotech.com/ECOS

It     pcost       dcost      gap   pres   dres    k/t    mu     step   sigma     IR    |   BT
 0  +0.000e+00  -0.000e+00  +0e+00  2e-15  0e+00  1e+00  1e+00    ---    ---    0  0  - |  -  - 

OPTIMAL (within feastol=2.4e-15, reltol=nan, abstol=0.0e+00).
Runtime: 0.000404 seconds.


julia> MOI.get(model, MOI.ConstraintDual(), c)
-0.0

julia> using ECOS

julia> const MOI = ECOS.MOI
MathOptInterface

julia> model = MOI.Utilities.CachingOptimizer(
           MOI.Utilities.UniversalFallback(MOI.Utilities.Model{Float64}()),
           MOI.instantiate(ECOS.Optimizer; with_bridge_type = Float64),
       )
MOIU.CachingOptimizer{MOIB.LazyBridgeOptimizer{MOIU.CachingOptimizer{ECOS.Optimizer, MOIU.UniversalFallback{MOIU.Model{Float64}}}}, MOIU.UniversalFallback{MOIU.Model{Float64}}}
in state EMPTY_OPTIMIZER
in mode AUTOMATIC
with model cache MOIU.UniversalFallback{MOIU.Model{Float64}}
  fallback for MOIU.Model{Float64}
with optimizer MOIB.LazyBridgeOptimizer{MOIU.CachingOptimizer{ECOS.Optimizer, MOIU.UniversalFallback{MOIU.Model{Float64}}}}
  with 0 variable bridges
  with 0 constraint bridges
  with 0 objective bridges
  with inner model MOIU.CachingOptimizer{ECOS.Optimizer, MOIU.UniversalFallback{MOIU.Model{Float64}}}
    in state EMPTY_OPTIMIZER
    in mode AUTOMATIC
    with model cache MOIU.UniversalFallback{MOIU.Model{Float64}}
      fallback for MOIU.Model{Float64}
    with optimizer ECOS.Optimizer

julia> x = MOI.add_variable(model)
MathOptInterface.VariableIndex(1)

julia> c = MOI.add_constraint(model, x, MOI.EqualTo(1.0))
MathOptInterface.ConstraintIndex{MathOptInterface.VariableIndex, MathOptInterface.EqualTo{Float64}}(1)

julia> MOI.optimize!(model)

julia> MOI.get(model, MOI.ConstraintDual(), c)
ERROR: ArgumentError: Bridge of type `MathOptInterface.Bridges.Variable.ZerosBridge{Float64}` does not support accessing the attribute `MathOptInterface.ConstraintDual(1)`. If you encountered this error unexpectedly, it probably means your model has been reformulated using the bridge, and you are attempting to query an attribute that we haven't implemented yet for this bridge. Please open an issue at https://github.com/jump-dev/MathOptInterface.jl/issues/new and provide a reproducible example explaining what you were trying to do.
Stacktrace:
  [1] get(#unused#::MathOptInterface.Bridges.LazyBridgeOptimizer{MathOptInterface.Utilities.CachingOptimizer{ECOS.Optimizer, MathOptInterface.Utilities.UniversalFallback{MathOptInterface.Utilities.Model{Float64}}}}, attr::MathOptInterface.ConstraintDual, bridge::MathOptInterface.Bridges.Variable.ZerosBridge{Float64})
    @ MathOptInterface.Bridges ~/.julia/packages/MathOptInterface/U4enZ/src/Bridges/bridge.jl:85
  [2] (::MathOptInterface.Bridges.var"#3#4"{typeof(MathOptInterface.get), MathOptInterface.Bridges.LazyBridgeOptimizer{MathOptInterface.Utilities.CachingOptimizer{ECOS.Optimizer, MathOptInterface.Utilities.UniversalFallback{MathOptInterface.Utilities.Model{Float64}}}}, MathOptInterface.ConstraintDual, Tuple{}})(bridge::MathOptInterface.Bridges.Variable.ZerosBridge{Float64})
    @ MathOptInterface.Bridges ~/.julia/packages/MathOptInterface/U4enZ/src/Bridges/bridge_optimizer.jl:308
  [3] (::MathOptInterface.Bridges.Variable.var"#23#24"{MathOptInterface.Bridges.Variable.Map, MathOptInterface.Bridges.var"#3#4"{typeof(MathOptInterface.get), MathOptInterface.Bridges.LazyBridgeOptimizer{MathOptInterface.Utilities.CachingOptimizer{ECOS.Optimizer, MathOptInterface.Utilities.UniversalFallback{MathOptInterface.Utilities.Model{Float64}}}}, MathOptInterface.ConstraintDual, Tuple{}}, Int64})()
    @ MathOptInterface.Bridges.Variable ~/.julia/packages/MathOptInterface/U4enZ/src/Bridges/Variable/map.jl:476
  [4] call_in_context(map::MathOptInterface.Bridges.Variable.Map, bridge_index::Int64, f::MathOptInterface.Bridges.Variable.var"#23#24"{MathOptInterface.Bridges.Variable.Map, MathOptInterface.Bridges.var"#3#4"{typeof(MathOptInterface.get), MathOptInterface.Bridges.LazyBridgeOptimizer{MathOptInterface.Utilities.CachingOptimizer{ECOS.Optimizer, MathOptInterface.Utilities.UniversalFallback{MathOptInterface.Utilities.Model{Float64}}}}, MathOptInterface.ConstraintDual, Tuple{}}, Int64})
    @ MathOptInterface.Bridges.Variable ~/.julia/packages/MathOptInterface/U4enZ/src/Bridges/Variable/map.jl:461
  [5] call_in_context
    @ ~/.julia/packages/MathOptInterface/U4enZ/src/Bridges/Variable/map.jl:476 [inlined]
  [6] call_in_context
    @ ~/.julia/packages/MathOptInterface/U4enZ/src/Bridges/bridge_optimizer.jl:269 [inlined]
  [7] call_in_context(b::MathOptInterface.Bridges.LazyBridgeOptimizer{MathOptInterface.Utilities.CachingOptimizer{ECOS.Optimizer, MathOptInterface.Utilities.UniversalFallback{MathOptInterface.Utilities.Model{Float64}}}}, ci::MathOptInterface.ConstraintIndex{MathOptInterface.VectorOfVariables, MathOptInterface.Zeros}, f::MathOptInterface.Bridges.var"#3#4"{typeof(MathOptInterface.get), MathOptInterface.Bridges.LazyBridgeOptimizer{MathOptInterface.Utilities.CachingOptimizer{ECOS.Optimizer, MathOptInterface.Utilities.UniversalFallback{MathOptInterface.Utilities.Model{Float64}}}}, MathOptInterface.ConstraintDual, Tuple{}})
    @ MathOptInterface.Bridges ~/.julia/packages/MathOptInterface/U4enZ/src/Bridges/bridge_optimizer.jl:288
  [8] call_in_context
    @ ~/.julia/packages/MathOptInterface/U4enZ/src/Bridges/bridge_optimizer.jl:305 [inlined]
  [9] get(b::MathOptInterface.Bridges.LazyBridgeOptimizer{MathOptInterface.Utilities.CachingOptimizer{ECOS.Optimizer, MathOptInterface.Utilities.UniversalFallback{MathOptInterface.Utilities.Model{Float64}}}}, attr::MathOptInterface.ConstraintDual, ci::MathOptInterface.ConstraintIndex{MathOptInterface.VectorOfVariables, MathOptInterface.Zeros})
    @ MathOptInterface.Bridges ~/.julia/packages/MathOptInterface/U4enZ/src/Bridges/bridge_optimizer.jl:1295
 [10] get(model::MathOptInterface.Bridges.LazyBridgeOptimizer{MathOptInterface.Utilities.CachingOptimizer{ECOS.Optimizer, MathOptInterface.Utilities.UniversalFallback{MathOptInterface.Utilities.Model{Float64}}}}, attr::MathOptInterface.ConstraintDual, bridge::MathOptInterface.Bridges.Variable.VectorizeBridge{Float64, MathOptInterface.Zeros})
    @ MathOptInterface.Bridges.Variable ~/.julia/packages/MathOptInterface/U4enZ/src/Bridges/Variable/vectorize.jl:127
 [11] (::MathOptInterface.Bridges.var"#3#4"{typeof(MathOptInterface.get), MathOptInterface.Bridges.LazyBridgeOptimizer{MathOptInterface.Utilities.CachingOptimizer{ECOS.Optimizer, MathOptInterface.Utilities.UniversalFallback{MathOptInterface.Utilities.Model{Float64}}}}, MathOptInterface.ConstraintDual, Tuple{}})(bridge::MathOptInterface.Bridges.Variable.VectorizeBridge{Float64, MathOptInterface.Zeros})
    @ MathOptInterface.Bridges ~/.julia/packages/MathOptInterface/U4enZ/src/Bridges/bridge_optimizer.jl:308
 [12] (::MathOptInterface.Bridges.Variable.var"#23#24"{MathOptInterface.Bridges.Variable.Map, MathOptInterface.Bridges.var"#3#4"{typeof(MathOptInterface.get), MathOptInterface.Bridges.LazyBridgeOptimizer{MathOptInterface.Utilities.CachingOptimizer{ECOS.Optimizer, MathOptInterface.Utilities.UniversalFallback{MathOptInterface.Utilities.Model{Float64}}}}, MathOptInterface.ConstraintDual, Tuple{}}, Int64})()
    @ MathOptInterface.Bridges.Variable ~/.julia/packages/MathOptInterface/U4enZ/src/Bridges/Variable/map.jl:476
 [13] call_in_context(map::MathOptInterface.Bridges.Variable.Map, bridge_index::Int64, f::MathOptInterface.Bridges.Variable.var"#23#24"{MathOptInterface.Bridges.Variable.Map, MathOptInterface.Bridges.var"#3#4"{typeof(MathOptInterface.get), MathOptInterface.Bridges.LazyBridgeOptimizer{MathOptInterface.Utilities.CachingOptimizer{ECOS.Optimizer, MathOptInterface.Utilities.UniversalFallback{MathOptInterface.Utilities.Model{Float64}}}}, MathOptInterface.ConstraintDual, Tuple{}}, Int64})
    @ MathOptInterface.Bridges.Variable ~/.julia/packages/MathOptInterface/U4enZ/src/Bridges/Variable/map.jl:461
 [14] call_in_context
    @ ~/.julia/packages/MathOptInterface/U4enZ/src/Bridges/Variable/map.jl:476 [inlined]
 [15] call_in_context
    @ ~/.julia/packages/MathOptInterface/U4enZ/src/Bridges/bridge_optimizer.jl:269 [inlined]
 [16] call_in_context
    @ ~/.julia/packages/MathOptInterface/U4enZ/src/Bridges/bridge_optimizer.jl:288 [inlined]
 [17] call_in_context
    @ ~/.julia/packages/MathOptInterface/U4enZ/src/Bridges/bridge_optimizer.jl:305 [inlined]
 [18] get(b::MathOptInterface.Bridges.LazyBridgeOptimizer{MathOptInterface.Utilities.CachingOptimizer{ECOS.Optimizer, MathOptInterface.Utilities.UniversalFallback{MathOptInterface.Utilities.Model{Float64}}}}, attr::MathOptInterface.ConstraintDual, ci::MathOptInterface.ConstraintIndex{MathOptInterface.VariableIndex, MathOptInterface.EqualTo{Float64}})
    @ MathOptInterface.Bridges ~/.julia/packages/MathOptInterface/U4enZ/src/Bridges/bridge_optimizer.jl:1295
 [19] get(model::MathOptInterface.Utilities.CachingOptimizer{MathOptInterface.Bridges.LazyBridgeOptimizer{MathOptInterface.Utilities.CachingOptimizer{ECOS.Optimizer, MathOptInterface.Utilities.UniversalFallback{MathOptInterface.Utilities.Model{Float64}}}}, MathOptInterface.Utilities.UniversalFallback{MathOptInterface.Utilities.Model{Float64}}}, attr::MathOptInterface.ConstraintDual, index::MathOptInterface.ConstraintIndex{MathOptInterface.VariableIndex, MathOptInterface.EqualTo{Float64}})
    @ MathOptInterface.Utilities ~/.julia/packages/MathOptInterface/U4enZ/src/Utilities/cachingoptimizer.jl:873
 [20] top-level scope
    @ REPL[14]:1

[blegat]

In the first case, it goes through the bridge layer as a constraint after creation so variable bridges cannot be applied. In the second case, copy_to passes it as a variable constrained on creation even though it was added to the cache after creation.

[blegat]

I don't see what this bridge has to do with x in EqualTo. It would get bridged to ScalarAffine-in-Zeros.

It can also be bridged to Zeros by Variable.VectorizeBridge

Are people really writing models with x in {0}?

No, that's why I'm talking about EqualTo, that's a more realistic use case.

[odow]

Yeah I originally thought this was because of our change to MatrixOfConstraints, but it's actually present in earlier versions as well. So perhaps it's not that much of a problem as I thought.

[odow]

@blegat and I discussed this offline. There's a few conflicting issues going on:

• The Clp issue was because we're writing VectorOfVariables([x]) in Zeros(1). No one would do this. But there are two bridging options: Scalarize to x in EqualTo(0.0), or through the ZerosBridge. In previous testing, we only had one cache so it went the scalarize way. In the new tests, we added as second cache outside the bridges so it got the opportunity to reformulate, and since we prefer variable bridges in general, it went the second route. In either case, this is okay because no one would write this constraint.
• The ECOS issue was x in EqualTo(1.0). And for the same reasons as Clp, the new cache exposed different behavior. But no one seems to have complained because this is an unusual constraint to add to a conic solver, and if you did, you'd probably want the replacement to happen.

So the conclusion is to leave it for now. And solvers encountering the duality error should remove the bridge in testing. We can revisit if we get anyone encountering this issue in the wild.