Chaining bridges doesn't work

[chriscoey]

If I run ]test on Hypatia on the branch https://github.com/chriscoey/Hypatia.jl/blob/318a20dd7f9c19ac62eb6914e1bdf6624439c25e/test/moi.jl#L76, with MOI dev'd on branch from #1178, I get an error from MOI:

  Test threw exception
  Expression: ≈(MOI.get(model, MOI.ConstraintPrimal(), gmc), [2.0; 2.0], atol = atol, rtol = rtol)
  
  Stacktrace:
   [1] throw_if_not_valid at /Users/coey/.julia/dev/MathOptInterface/src/indextypes.jl:75 [inlined]
   [2] get(::MathOptInterface.Bridges.Constraint.SingleBridgeOptimizer{MathOptInterface.Bridges.Constraint.RelativeEntropyBridge{Float64,F,G,H} where H where G where F,MathOptInterface.Bridges.Constraint.SingleBridgeOptimizer{MathOptInterface.Bridges.Constraint.GeoMeantoRelEntrBridge{Float64,F,G,H} where H where G where F,MathOptInterface.Utilities.CachingOptimizer{Hypatia.Optimizer{Float64},MathOptInterface.Utilities.UniversalFallback{MathOptInterface.Utilities.Model{Float64}}}}}, ::MathOptInterface.ConstraintPrimal, ::MathOptInterface.ConstraintIndex{MathOptInterface.VectorOfVariables,MathOptInterface.GeometricMeanCone}) at /Users/coey/.julia/dev/MathOptInterface/src/Bridges/bridge_optimizer.jl:919
   [3] _geomean3test(::MathOptInterface.Bridges.Constraint.SingleBridgeOptimizer{MathOptInterface.Bridges.Constraint.RelativeEntropyBridge{Float64,F,G,H} where H where G where F,MathOptInterface.Bridges.Constraint.SingleBridgeOptimizer{MathOptInterface.Bridges.Constraint.GeoMeantoRelEntrBridge{Float64,F,G,H} where H where G where F,MathOptInterface.Utilities.CachingOptimizer{Hypatia.Optimizer{Float64},MathOptInterface.Utilities.UniversalFallback{MathOptInterface.Utilities.Model{Float64}}}}}, ::MathOptInterface.Test.TestConfig{Float64}, ::Bool) at /Users/coey/.julia/dev/MathOptInterface/src/Test/contconic.jl:1546
   [4] geomean3vtest(::MathOptInterface.Bridges.Constraint.SingleBridgeOptimizer{MathOptInterface.Bridges.Constraint.RelativeEntropyBridge{Float64,F,G,H} where H where G where F,MathOptInterface.Bridges.Constraint.SingleBridgeOptimizer{MathOptInterface.Bridges.Constraint.GeoMeantoRelEntrBridge{Float64,F,G,H} where H where G where F,MathOptInterface.Utilities.CachingOptimizer{Hypatia.Optimizer{Float64},MathOptInterface.Utilities.UniversalFallback{MathOptInterface.Utilities.Model{Float64}}}}}, ::MathOptInterface.Test.TestConfig{Float64}) at /Users/coey/.julia/dev/MathOptInterface/src/Test/contconic.jl:1556
   [5] macro expansion at /Users/coey/.julia/dev/MathOptInterface/src/Test/config.jl:48 [inlined]
   [6] macro expansion at /Users/coey/julia/usr/share/julia/stdlib/v1.5/Test/src/Test.jl:1115 [inlined]
   [7] geomeantest(::MathOptInterface.Bridges.Constraint.SingleBridgeOptimizer{MathOptInterface.Bridges.Constraint.RelativeEntropyBridge{Float64,F,G,H} where H where G where F,MathOptInterface.Bridges.Constraint.SingleBridgeOptimizer{MathOptInterface.Bridges.Constraint.GeoMeantoRelEntrBridge{Float64,F,G,H} where H where G where F,MathOptInterface.Utilities.CachingOptimizer{Hypatia.Optimizer{Float64},MathOptInterface.Utilities.UniversalFallback{MathOptInterface.Utilities.Model{Float64}}}}}, ::MathOptInterface.Test.TestConfig{Float64}, ::Array{String,1}) at /Users/coey/.julia/dev/MathOptInterface/src/Test/config.jl:48

specifically, excluding all conic tests except the geomean tests, the failure happens on the second line below but not the first:

MOIT.contconictest(MOI.Bridges.Constraint.GeoMeantoRelEntr{T}(MOI.Bridges.Constraint.RelativeEntropy{T}(optimizer)), config, conic_exclude)
MOIT.contconictest(MOI.Bridges.Constraint.RelativeEntropy{T}(MOI.Bridges.Constraint.GeoMeantoRelEntr{T}(optimizer)), config, conic_exclude)

with the only difference being the order of application of those two bridges. The first line successfully bridges the geomean cone to exponential cones via the relative entropy cone (see #1178).
@blegat my guess is this isn't a problem introduced in #1178 so hopefully it doesn't block that.

[blegat]

With MOI and Hypatia master, I get:

julia> T = Float64; optimizer = MOIU.CachingOptimizer(MOIU.UniversalFallback(MOIU.Model{T}()), Hypatia.Optimizer{T}());

julia> MOIT.geomean3vtest(MOI.Bridges.Constraint.RelativeEntropy{T}(MOI.Bridges.Constraint.GeoMeantoRelEntr{T}(optimizer)), config)

 iter        p_obj        d_obj   abs_gap    x_feas    z_feas       tau       kap        mu     gamma     alpha
    0   3.8980e-01  -1.4142e+00  5.00e+00  8.22e-01  3.43e-01  1.00e+00  1.00e+00  1.00e+00
    1  -2.7223e+00  -2.5075e+00  9.56e-01  3.02e-01  1.26e-01  6.17e-01  7.67e-01  2.38e-01  1.86e-01  9.50e-01
    2  -3.1096e+00  -3.2930e+00  7.74e-01  2.06e-01  8.58e-02  5.81e-01  3.01e-01  1.58e-01  6.42e-01  1.00e+00
...
  150  -4.0000e+00  -4.0000e+00  1.65e-11  8.24e-01  5.45e-11  1.70e-01  1.94e-11  3.30e-12  1.00e+00  1.00e+00
  151  -4.0000e+00  -4.0000e+00  1.65e-11  8.24e-01  5.45e-11  1.70e-01  1.94e-11  3.30e-12  1.00e+00  1.00e+00
slow progress in consecutive iterations; terminating

status is SlowProgress after 151 iterations and 19.044 seconds

Test Failed at /home/blegat/.julia/dev/MathOptInterface/src/Test/contconic.jl:1538
  Expression: MOI.get(model, MOI.TerminationStatus()) == config.optimal_status
   Evaluated: MathOptInterface.SLOW_PROGRESS == MathOptInterface.OPTIMAL
ERROR: There was an error during testing

and I get the same thing using the commit 318a20dd7f9c19ac62eb6914e1bdf6624439c25e of Hypatia
The versioninfo is

julia> versioninfo()
Julia Version 1.5.2
Commit 539f3ce943 (2020-09-23 23:17 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
  CPU: Intel(R) Core(TM) i7-6700HQ CPU @ 2.60GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-9.0.1 (ORCJIT, skylake)

[odow]

Is there anything to do here? This looks like a convergence issue in Hypatia.

[chriscoey]

that convergence issue was unrelated, and I didn't see it locally.
see jump-dev/Hypatia.jl#688 - the error still occurs with most recent release of MOI.
eg from CI on that PR:

The index MathOptInterface.ConstraintIndex{MathOptInterface.VectorOfVariables, MathOptInterface.GeometricMeanCone}(-1) is invalid. Note that an index becomes invalid after it has been deleted.geomean1v: Error During Test at /home/runner/.julia/packages/MathOptInterface/1EYfq/src/Test/contconic.jl:2422
  Test threw exception
  Expression: ≈(MOI.get(model, MOI.ConstraintPrimal(), gmc), ones(n + 1), atol = atol, rtol = rtol)
  
  Stacktrace:
   [1] throw_if_not_valid
     @ ~/.julia/packages/MathOptInterface/1EYfq/src/indextypes.jl:77 [inlined]
   [2] get(b::MathOptInterface.Bridges.Constraint.SingleBridgeOptimizer{MathOptInterface.Bridges.Constraint.RelativeEntropyBridge{Float64, F, G, H} where {F, G, H}, MathOptInterface.Bridges.Constraint.SingleBridgeOptimizer{MathOptInterface.Bridges.Constraint.GeoMeantoRelEntrBridge{Float64, F, G, H} where {F, G, H}, MathOptInterface.Utilities.CachingOptimizer{Hypatia.Optimizer{Float64}, MathOptInterface.Utilities.UniversalFallback{MathOptInterface.Utilities.GenericModel{Float64, MathOptInterface.Utilities.ModelFunctionConstraints{Float64}}}}}}, attr::MathOptInterface.ConstraintPrimal, ci::MathOptInterface.ConstraintIndex{MathOptInterface.VectorOfVariables, MathOptInterface.GeometricMeanCone})
     @ MathOptInterface.Bridges ~/.julia/packages/MathOptInterface/1EYfq/src/Bridges/bridge_optimizer.jl:1126
   [3] _geomean1test(model::MathOptInterface.Bridges.Constraint.SingleBridgeOptimizer{MathOptInterface.Bridges.Constraint.RelativeEntropyBridge{Float64, F, G, H} where {F, G, H}, MathOptInterface.Bridges.Constraint.SingleBridgeOptimizer{MathOptInterface.Bridges.Constraint.GeoMeantoRelEntrBridge{Float64, F, G, H} where {F, G, H}, MathOptInterface.Utilities.CachingOptimizer{Hypatia.Optimizer{Float64}, MathOptInterface.Utilities.UniversalFallback{MathOptInterface.Utilities.GenericModel{Float64, MathOptInterface.Utilities.ModelFunctionConstraints{Float64}}}}}}, config::MathOptInterface.Test.TestConfig{Float64}, vecofvars::Bool, n::Int64)
     @ MathOptInterface.Test ~/.julia/packages/MathOptInterface/1EYfq/src/Test/contconic.jl:2422
   [4] _geomean1test
     @ ~/.julia/packages/MathOptInterface/1EYfq/src/Test/contconic.jl:2322 [inlined]
   [5] geomean1vtest(model::MathOptInterface.Bridges.Constraint.SingleBridgeOptimizer{MathOptInterface.Bridges.Constraint.RelativeEntropyBridge{Float64, F, G, H} where {F, G, H}, MathOptInterface.Bridges.Constraint.SingleBridgeOptimizer{MathOptInterface.Bridges.Constraint.GeoMeantoRelEntrBridge{Float64, F, G, H} where {F, G, H}, MathOptInterface.Utilities.CachingOptimizer{Hypatia.Optimizer{Float64}, MathOptInterface.Utilities.UniversalFallback{MathOptInterface.Utilities.GenericModel{Float64, MathOptInterface.Utilities.ModelFunctionConstraints{Float64}}}}}}, config::MathOptInterface.Test.TestConfig{Float64})
     @ MathOptInterface.Test ~/.julia/packages/MathOptInterface/1EYfq/src/Test/contconic.jl:2438
   [6] macro expansion
     @ ~/.julia/packages/MathOptInterface/1EYfq/src/Test/config.jl:70 [inlined]
   [7] macro expansion
     @ /buildworker/worker/package_linux64/build/usr/share/julia/stdlib/v1.6/Test/src/Test.jl:1151 [inlined]
   [8] geomeantest(model::MathOptInterface.Bridges.Constraint.SingleBridgeOptimizer{MathOptInterface.Bridges.Constraint.RelativeEntropyBridge{Float64, F, G, H} where {F, G, H}, MathOptInterface.Bridges.Constraint.SingleBridgeOptimizer{MathOptInterface.Bridges.Constraint.GeoMeantoRelEntrBridge{Float64, F, G, H} where {F, G, H}, MathOptInterface.Utilities.CachingOptimizer{Hypatia.Optimizer{Float64}, MathOptInterface.Utilities.UniversalFallback{MathOptInterface.Utilities.GenericModel{Float64, MathOptInterface.Utilities.ModelFunctionConstraints{Float64}}}}}}, config::MathOptInterface.Test.TestConfig{Float64}, exclude::Vector{String})
     @ MathOptInterface.Test ~/.julia/packages/MathOptInterface/1EYfq/src/Test/config.jl:70

[odow]

Okay, I'll take a look.

[odow]

Reproduced without Hypatia:

using MathOptInterface
const MOI = MathOptInterface
model = MOI.Bridges.Constraint.RelativeEntropy{Float64}(
    MOI.Bridges.Constraint.GeoMeantoRelEntr{Float64}(
        MOI.Utilities.Model{Float64}(),
    ),
)
x = MOI.add_variables(model, 2)
c = MOI.add_constraint(model, MOI.VectorOfVariables(x), MOI.GeometricMeanCone(2))
@assert MOI.is_valid(model, c)

@blegat, I like our new printing:

julia> using MathOptInterface

julia> const MOI = MathOptInterface
MathOptInterface

julia> m0 = MOI.Utilities.Model{Float64}()
MOIU.GenericModel{Float64, MOIU.ModelFunctionConstraints{Float64}}

julia> m1 = MOI.Bridges.Constraint.GeoMeantoRelEntr{Float64}(m0)
MOIB.Constraint.SingleBridgeOptimizer{MOIB.Constraint.GeoMeantoRelEntrBridge{Float64, F, G, H} where {F, G, H}, MOIU.GenericModel{Float64, MOIU.ModelFunctionConstraints{Float64}}}
with 0 constraint bridges
with inner model MOIU.GenericModel{Float64, MOIU.ModelFunctionConstraints{Float64}}

julia> m2 = MOI.Bridges.Constraint.RelativeEntropy{Float64}(m1)
MOIB.Constraint.SingleBridgeOptimizer{MOIB.Constraint.RelativeEntropyBridge{Float64, F, G, H} where {F, G, H}, MOIB.Constraint.SingleBridgeOptimizer{MOIB.Constraint.GeoMeantoRelEntrBridge{Float64, F, G, H} where {F, G, H}, MOIU.GenericModel{Float64, MOIU.ModelFunctionConstraints{Float64}}}}
with 0 constraint bridges
with inner model MOIB.Constraint.SingleBridgeOptimizer{MOIB.Constraint.GeoMeantoRelEntrBridge{Float64, F, G, H} where {F, G, H}, MOIU.GenericModel{Float64, MOIU.ModelFunctionConstraints{Float64}}}
  with 0 constraint bridges
  with inner model MOIU.GenericModel{Float64, MOIU.ModelFunctionConstraints{Float64}}

julia> x = MOI.add_variables(m2, 2)
2-element Vector{MathOptInterface.VariableIndex}:
 MathOptInterface.VariableIndex(1)
 MathOptInterface.VariableIndex(2)

julia> c = MOI.add_constraint(m2, MOI.VectorOfVariables(x), MOI.GeometricMeanCone(2))
MathOptInterface.ConstraintIndex{MathOptInterface.VectorOfVariables, MathOptInterface.GeometricMeanCone}(-1)

julia> @assert MOI.is_valid(m2, c)
ERROR: AssertionError: MOI.is_valid(m2, c)
Stacktrace:
 [1] top-level scope
   @ REPL[27]:1

julia> print(m0)
Feasibility

Subject to:

VectorOfVariables-in-Nonnegatives
 ┌    ┐
 │v[3]│
 └    ┘ ∈ Nonnegatives(1)

VectorAffineFunction{Float64}-in-RelativeEntropyCone
 ┌                         ┐
 │0.0                      │
 │0.0 + 1.0 v[2]           │
 │0.0 + 1.0 v[1] + 1.0 v[3]│
 └                         ┘ ∈ RelativeEntropyCone(3)

julia> print(m1)
Feasibility

Subject to:

VectorOfVariables-in-GeometricMeanCone
 ┌    ┐
 │v[1]│
 │v[2]│
 └    ┘ ∈ GeometricMeanCone(2)

julia> print(m2)
Feasibility

Subject to:

VectorOfVariables-in-GeometricMeanCone
ERROR: The index MathOptInterface.ConstraintIndex{MathOptInterface.VectorOfVariables, MathOptInterface.GeometricMeanCone}(-1) is invalid. Note that an index becomes invalid after it has been deleted.
Stacktrace:
 [1] throw_if_not_valid
   @ ~/.julia/dev/MathOptInterface/src/indextypes.jl:77 [inlined]
 [2] get(b::MathOptInterface.Bridges.Constraint.SingleBridgeOptimizer{MathOptInterface.Bridges.Constraint.RelativeEntropyBridge{Float64, F, G, H} where {F, G, H}, MathOptInterface.Bridges.Constraint.SingleBridgeOptimizer{MathOptInterface.Bridges.Constraint.GeoMeantoRelEntrBridge{Float64, F, G, H} where {F, G, H}, MathOptInterface.Utilities.GenericModel{Float64, MathOptInterface.Utilities.ModelFunctionConstraints{Float64}}}}, attr::MathOptInterface.ConstraintFunction, ci::MathOptInterface.ConstraintIndex{MathOptInterface.VectorOfVariables, MathOptInterface.GeometricMeanCone})
   @ MathOptInterface.Bridges ~/.julia/dev/MathOptInterface/src/Bridges/bridge_optimizer.jl:1052
 [3] _to_string(options::MathOptInterface.Utilities._PrintOptions{MIME{Symbol("text/plain")}}, model::MathOptInterface.Bridges.Constraint.SingleBridgeOptimizer{MathOptInterface.Bridges.Constraint.RelativeEntropyBridge{Float64, F, G, H} where {F, G, H}, MathOptInterface.Bridges.Constraint.SingleBridgeOptimizer{MathOptInterface.Bridges.Constraint.GeoMeantoRelEntrBridge{Float64, F, G, H} where {F, G, H}, MathOptInterface.Utilities.GenericModel{Float64, MathOptInterface.Utilities.ModelFunctionConstraints{Float64}}}}, cref::MathOptInterface.ConstraintIndex{MathOptInterface.VectorOfVariables, MathOptInterface.GeometricMeanCone})
   @ MathOptInterface.Utilities ~/.julia/dev/MathOptInterface/src/Utilities/print.jl:360
 [4] _print_model(io::Base.TTY, options::MathOptInterface.Utilities._PrintOptions{MIME{Symbol("text/plain")}}, model::MathOptInterface.Bridges.Constraint.SingleBridgeOptimizer{MathOptInterface.Bridges.Constraint.RelativeEntropyBridge{Float64, F, G, H} where {F, G, H}, MathOptInterface.Bridges.Constraint.SingleBridgeOptimizer{MathOptInterface.Bridges.Constraint.GeoMeantoRelEntrBridge{Float64, F, G, H} where {F, G, H}, MathOptInterface.Utilities.GenericModel{Float64, MathOptInterface.Utilities.ModelFunctionConstraints{Float64}}}})
   @ MathOptInterface.Utilities ~/.julia/dev/MathOptInterface/src/Utilities/print.jl:554
 [5] #print#274
   @ ~/.julia/dev/MathOptInterface/src/Utilities/print.jl:648 [inlined]
 [6] print(io::Base.TTY, model::MathOptInterface.Bridges.Constraint.SingleBridgeOptimizer{MathOptInterface.Bridges.Constraint.RelativeEntropyBridge{Float64, F, G, H} where {F, G, H}, MathOptInterface.Bridges.Constraint.SingleBridgeOptimizer{MathOptInterface.Bridges.Constraint.GeoMeantoRelEntrBridge{Float64, F, G, H} where {F, G, H}, MathOptInterface.Utilities.GenericModel{Float64, MathOptInterface.Utilities.ModelFunctionConstraints{Float64}}}})
   @ MathOptInterface.Utilities ~/.julia/dev/MathOptInterface/src/Utilities/print.jl:648
 [7] print(model::MathOptInterface.Bridges.Constraint.SingleBridgeOptimizer{MathOptInterface.Bridges.Constraint.RelativeEntropyBridge{Float64, F, G, H} where {F, G, H}, MathOptInterface.Bridges.Constraint.SingleBridgeOptimizer{MathOptInterface.Bridges.Constraint.GeoMeantoRelEntrBridge{Float64, F, G, H} where {F, G, H}, MathOptInterface.Utilities.GenericModel{Float64, MathOptInterface.Utilities.ModelFunctionConstraints{Float64}}}}; kwargs::Base.Iterators.Pairs{Union{}, Union{}, Tuple{}, NamedTuple{(), Tuple{}}})
   @ MathOptInterface.Utilities ~/.julia/dev/MathOptInterface/src/Utilities/print.jl:644
 [8] print(model::MathOptInterface.Bridges.Constraint.SingleBridgeOptimizer{MathOptInterface.Bridges.Constraint.RelativeEntropyBridge{Float64, F, G, H} where {F, G, H}, MathOptInterface.Bridges.Constraint.SingleBridgeOptimizer{MathOptInterface.Bridges.Constraint.GeoMeantoRelEntrBridge{Float64, F, G, H} where {F, G, H}, MathOptInterface.Utilities.GenericModel{Float64, MathOptInterface.Utilities.ModelFunctionConstraints{Float64}}}})
   @ MathOptInterface.Utilities ~/.julia/dev/MathOptInterface/src/Utilities/print.jl:638
 [9] top-level scope
   @ REPL[30]:1

[odow]

@blegat I'm surprised this hasn't come up earlier.

using MathOptInterface
const MOI = MathOptInterface
m0 = MOI.Utilities.Model{Float64}()
m1 = MOI.Bridges.Constraint.GeoMeantoRelEntr{Float64}(m0)
m2 = MOI.Bridges.Constraint.RelativeEntropy{Float64}(m1)
x = MOI.add_variables(m2, 2)
c = MOI.add_constraint(m2, MOI.VectorOfVariables(x), MOI.GeometricMeanCone(2))
@assert MOI.is_valid(m2, c)

The issue is that the constraint gets bridged by m1, so the constraint index is returned as -1, which causes is_variable-bridged(m2, c) == true, but m2 didn't do the bridging.

MathOptInterface.jl/src/Bridges/bridge_optimizer.jl

Lines 376 to 391 in 85f9703

	function MOI.is_valid(
	b::AbstractBridgeOptimizer,
	ci::MOI.ConstraintIndex{F,S},
	) where {F,S}
	if is_bridged(b, ci)
	if is_variable_bridged(b, ci)
	vi = MOI.VariableIndex(ci.value)
	return MOI.is_valid(b, vi) &&
	Variable.constrained_set(Variable.bridges(b), vi) == S
	else
	return haskey(Constraint.bridges(b), ci)
	end
	else
	return MOI.is_valid(b.model, ci)
	end
	end

Ideas?

[blegat]

This is disallowed for this reason in the docstring:

MathOptInterface.jl/src/Bridges/Variable/single_bridge_optimizer.jl

Lines 9 to 12 in 2c1666d

	!!! note
	Two bridge optimizers using variable bridges cannot be used together as both
	of them assume that the underlying model only returns variable indices with
	nonnegative values.

[odow]

This is with constraint bridges though. I guess VectorOfVariable constraint bridges are special? Maybe it just needs to be better documented.

[blegat]

Indeed, the indexing changed for constraint bridges in #1125. So if a SingleVariable or VectorOfVariables has bridged variables, it will be bridged by FunctionizeBridge even if the constraint is supported. We use negative indices to avoid clashes with the inner model as it supports this type of constraints so both the inner model and the bridge optimizer uses indices for this type.
However, this can only happen if you use variable bridges. One corner case I haven't thought of though is that if an inner layer uses variable bridges then an outer layer may bridge constraints (because it sees negative indices) even if it does not do any variables bridges. That isn't covered by the doc.
The new rule "the inner model of a LazyBridgeOptimizer should not do any variable bridging" still works (once we have the fix #1322)