Failure with SOS1 reformulation

[frapac]

The SOS1 reformulation fails on this LPCC example:

using JuMP
using ComplementOpt
using HiGHS

model = Model()
@variable(model, 0 <= z1, start=0.0)
@variable(model, 0 <= z2, start=1.0)
@variable(model, z3, start=0.0)
# z3 = 1.0
@objective(model, Min, z1 + z2 - z3)
@constraint(model, -4 * z1 + z3 <= 0)
@constraint(model, -4 * z2 + z3 <= 0)
@constraint(model, comp, [z1, z2] ∈ MOI.Complements(2))

JuMP.set_optimizer(model, () -> ComplementOpt.Optimizer(
        MOI.Bridges.full_bridge_optimizer(HiGHS.Optimizer(), Float64)
    )
)
JuMP.optimize!(model)

Returning an error in final_touch:

ERROR: LoadError: MathOptInterface.Bridges.BridgeRequiresFiniteDomainError{MathOptInterface.Bridges.Constraint.SOS1ToMILPBridge{Float64, MathOptInterface.VectorOfVariables}, MathOptInterface.VariableIndex}:                                 
                                                                                                                                                                                                                                               
There was an error reformulating your model into a form supported by the                                                                                                                                                                       
solver because one of the bridges requires that all variables have a                                                                                                                                                                           
finite domain.  

The error remains if I add bound on z1 and z2. I am wondering what would be the correct usage for the SOS1 bridge? Should we allow the user to pass the big-M constraint manually?

[blegat]

What would you expect the MILP formulation to be ?

[frapac]

Good question. I don't see any good solution if the users do not provide the big-M constant by themselves.

I think we can use HiGHS in our tests, so we can test the SOS1 bridge in our pipeline. I guess that most people interested into the SOS1 formulation will use a solver that supports SOS1 for that purpose.

I would be good to test MathOptComplements with Gurobi, just to see how easy is it to solve a MPCC with the SOS1 formulation. I can take care of this.

[blegat]

One solution would be to add a bridge attribute for SOS1ToMILPBridge that is the big-M constant but we might as well ask the user to add this as bounds to z1 and z2 ?

[frapac]

I am in favor of using the easiest solution. Specifying the bounds in z1 and z2 is fine by me, but what if the bridges add new variables with only a lower bound?

[blegat]

At the moment, the bridge just change the set, it's just the same variables. You can see that func is passed as-is:
https://github.com/blegat/MathOptComplements.jl/blob/fa2a4f69dd570ded8cd35d606f893d6f996e9acf/src/Bridges/to_sos1_bridge.jl#L33-L37

[frapac]

MWE with big-M introduced manually:

using JuMP
using MathOptComplements
using HiGHS

big_M = 1e3

model = Model()
@variable(model, 0 <= z1 <= big_M, start=0.0)
@variable(model, 0 <= z2 <= big_M, start=1.0)
@variable(model, z3, start=0.0)
# z3 = 1.0
@objective(model, Min, z1 + z2 - z3)
@constraint(model, -4 * z1 + z3 <= 0)
@constraint(model, -4 * z2 + z3 <= 0)
@constraint(model, comp, [z1, z2] ∈ MOI.Complements(2))

JuMP.set_optimizer(model, () -> MathOptComplements.Optimizer(
        MOI.Bridges.full_bridge_optimizer(HiGHS.Optimizer(), Float64)
    )
)
JuMP.optimize!(model)

[odow]

julia> using JuMP

julia> import MathOptComplements

julia> import HiGHS

julia> begin
           model = Model() do
               inner = MOI.instantiate(HiGHS.Optimizer; with_bridge_type = Float64)
               return MathOptComplements.Optimizer(inner)
           end
           @variable(model, 0 <= z[1:2] <= 1e3)
           @variable(model, z3)
           @objective(model, Min, sum(z) - z3)
           @constraint(model, z3 .<= 4 .* z)
           @constraint(model, z in MOI.Complements(2))
           optimize!(model)
       end
Running HiGHS 1.14.0 (git hash: 7df0786de3): Copyright (c) 2026 under Apache 2.0 license terms
Using BLAS: blastrampoline 
ERROR: MathOptInterface.Bridges.BridgeRequiresFiniteDomainError{MathOptInterface.Bridges.Constraint.SOS1ToMILPBridge{Float64, MathOptInterface.VectorOfVariables}, MathOptInterface.VariableIndex}:

There was an error reformulating your model into a form supported by the
solver because one of the bridges requires that all variables have a
finite domain.

To fix this error, add a lower and upper bound to all variables in your
model.

If you have double checked that all variables have finite bounds and you
are still encountering this issue, please open a GitHub issue at
https://github.com/jump-dev/MathOptInterface.jl

## Common mistakes

A common mistake is to add the variable bounds as affine constraints. For
example, if you are using JuMP, do not use `@constraint` to add variable
bounds:
```julia
using JuMP
model = Model()
@variable(model, x)
@constraint(model, x >= 0)
@constraint(model, x <= 1)
```
do instead:
```julia
using JuMP
model = Model()
@variable(model, 0 <= x <= 1)
```

## Large bound values

Do not add arbitrarily large variable bounds to fix this error. Doing so
will likely result in a reformulation that takes a long time to build
and solve. Use domain knowledge to find the tightest valid bounds.

Alternatively, use a solver that has native support for the constraint
types you are using so that you do not need to use the bridging system.

Stacktrace:
  [1] final_touch(bridge::MathOptInterface.Bridges.Constraint.SOS1ToMILPBridge{…}, model::MathOptInterface.Bridges.LazyBridgeOptimizer{…})
    @ MathOptInterface.Bridges.Constraint ~/.julia/packages/MathOptInterface/EMtxt/src/Bridges/Constraint/bridges/SOS1ToMILPBridge.jl:215
  [2] _final_touch(bridges::OrderedCollections.OrderedSet{…}, model::MathOptInterface.Bridges.LazyBridgeOptimizer{…})
    @ MathOptInterface.Bridges.Constraint ~/.julia/packages/MathOptInterface/EMtxt/src/Bridges/Constraint/map.jl:340
  [3] final_touch(map::MathOptInterface.Bridges.Constraint.Map, model::MathOptInterface.Bridges.LazyBridgeOptimizer{…})
    @ MathOptInterface.Bridges.Constraint ~/.julia/packages/MathOptInterface/EMtxt/src/Bridges/Constraint/map.jl:347
  [4] final_touch
    @ ~/.julia/packages/MathOptInterface/EMtxt/src/Bridges/bridge_optimizer.jl:456 [inlined]
  [5] final_touch
    @ ~/.julia/packages/MathOptInterface/EMtxt/src/Bridges/bridge_optimizer.jl:461 [inlined]
  [6] final_touch (repeats 2 times)
    @ ~/.julia/packages/MathOptInterface/EMtxt/src/Bridges/bridge_optimizer.jl:462 [inlined]
  [7] default_copy_to(dest::MathOptInterface.Bridges.LazyBridgeOptimizer{…}, src::MathOptInterface.Utilities.UniversalFallback{…})
    @ MathOptInterface.Utilities ~/.julia/packages/MathOptInterface/EMtxt/src/Utilities/copy.jl:394
  [8] copy_to
    @ ~/.julia/packages/MathOptInterface/EMtxt/src/Bridges/bridge_optimizer.jl:448 [inlined]
  [9] optimize!
    @ ~/.julia/packages/MathOptInterface/EMtxt/src/MathOptInterface.jl:121 [inlined]
 [10] optimize!(m::MathOptInterface.Utilities.CachingOptimizer{…})
    @ MathOptInterface.Utilities ~/.julia/packages/MathOptInterface/EMtxt/src/Utilities/cachingoptimizer.jl:370
 [11] optimize!(model::Model; ignore_optimize_hook::Bool, _differentiation_backend::MathOptInterface.Nonlinear.SparseReverseMode, kwargs::@Kwargs{})
    @ JuMP ~/.julia/packages/JuMP/EHXNP/src/optimizer_interface.jl:610
 [12] optimize!(model::Model)
    @ JuMP ~/.julia/packages/JuMP/EHXNP/src/optimizer_interface.jl:560
 [13] top-level scope
    @ REPL[15]:11
Some type information was truncated. Use `show(err)` to see complete types.

[odow]

Without digging in, this seems like a bug either in MOI.is_valid, or in how you're getting/setting attributes between MathOptComplements and the inner optimizer.

[odow]

Unless it's this: jump-dev/MathOptInterface.jl#1980

[blegat]

Claude analysis:
Variable numbering from the run: v1 = z[1], v2 = z[2],
v3 = z3, and v4, v5, v6 are bridge-created (I'll call them xp, xn, s).

Stage 0 — what MathOptComplements.Optimizer receives. Everything below except the Complements constraint is passed through untouched to
the inner solver, so I only track that one constraint afterwards:

min z1 + z2 - z3
z1, z2 ∈ [0, 1000], z3 free
z3 - 4 z1 ≤ 0, z3 - 4 z2 ≤ 0
[z1, z2] ∈ Complements(2) (VectorOfVariables)

Bridge 1 — SpecifySetTypeBridge (runs in final_touch because it needs bounds). It reads the bounds of the second variable z2: both 0 and
1000 are finite, so it takes the _specify_range! branch. No bound is added on z1 in this branch. The constraint becomes:

[z1, z2] ∈ ComplementsWithSetType{Interval{Float64}}(2)

Bridge 2 — SplitIntervalBridge splits the activity z1 into a positive and negative part. This is where the first unbounded variables
appear:

new variables: xp ≥ 0 (v4, no upper bound)
xn ≤ 0 (v5, no lower bound)
new constraint: z1 - xp - xn = 0 (SAF-in-EqualTo → HiGHS)
replaced by: A: [xp, z2] ∈ ComplementsWithSetType{GreaterThan{Float64}}(2) (VOV)
B: [xn, z2] ∈ ComplementsWithSetType{LessThan{Float64}}(2) (VOV)

Branch A ([xp, z2], three bridges):

1. ComplementsVectorizeBridge{…,GreaterThan,Nonnegatives}: reads lb(z2) = 0 and shifts the second component. Since the shift is 0 the
   model is unchanged mathematically, but the function becomes a VectorAffineFunction: [1·xp, 1·z2 - 0] ∈
   ComplementsWithSetType{Nonnegatives}(2).
2. VerticalBridge{…,Nonnegatives}: both components are recognized as plain variables (coefficient +1, no constant), so no slack is added;
   it just converts back to VectorOfVariables: [xp, z2] ∈ ComplementsWithSetType{Nonnegatives}(2).
3. ToSOS1Bridge: [xp, z2] ∈ SOS1([1.0, 2.0]).

Branch B ([xn, z2], five bridges — one more round-trip than branch A):

1. FlipSignBridge{…,LessThan,GreaterThan}: negates the activity, producing an affine function: [-1·xn, 1·z2] ∈
   ComplementsWithSetType{GreaterThan{Float64}}(2).
2. VerticalBridge{…,GreaterThan}: -1·xn has coefficient -1, so _is_single_variable is false and it creates a completely free slack s (v6,
   via bare MOI.add_variable, no bounds) with the equality -xn - s = 0, giving [s, z2] ∈ ComplementsWithSetType{GreaterThan{Float64}}(2).
3. ComplementsVectorizeBridge: shift by lb(z2) = 0 again → [1·s, 1·z2] ∈ ComplementsWithSetType{Nonnegatives}(2) (VAF).
4. VerticalBridge{…,Nonnegatives}: both plain variables, no slack → [s, z2] ∈ ComplementsWithSetType{Nonnegatives}(2) (VOV).
5. ToSOS1Bridge: [s, z2] ∈ SOS1([1.0, 2.0]).

Final model handed to the inner LazyBridgeOptimizer{HiGHS.Optimizer} (dumped from the failed run, verbatim):

min z1 + z2 - z3
z1, z2 ∈ [0, 1000], z3 free
xp ∈ [0, ∞), xn ∈ (-∞, 0], s free
z3 - 4 z1 ≤ 0, z3 - 4 z2 ≤ 0
z1 - xp - xn = 0
-xn - s = 0
[xp, z2] ∈ SOS1([1.0, 2.0])
[s, z2] ∈ SOS1([1.0, 2.0])

HiGHS has no native SOS1, so the inner bridge layer applies SOS1ToMILPBridge to both SOS1 constraints. Its final_touch requires finite
bounds on every variable in the SOS1 function; it hits xp ∈ [0, ∞) in the first one and throws on MOI.VariableIndex(4). Even if xp were
bounded, the second SOS1 would fail on the free slack s.

So of the three problematic variables, xp/xn come from SplitIntervalBridge (half-bounded) and s from VerticalBridge under FlipSignBridge
(fully free) — and all three have derivable finite bounds (xp ∈ [0, max(ub(z1), 0)], xn ∈ [min(lb(z1), 0), 0], and s = -xn so s ∈ [0,
-lb(xn)]) that the bridges simply don't set.