Complement -> Indicator Bridge

[matbesancon]

In order to leverage MILP solvers for linear complementarity problems, indicator constraints seem rather natural, with a bridge introducing binary variables. Two formulations would be:

(F1)

(zl,zu,zint) in {0,1}
x in Interval(lb, ub)

zl = 1 -> {F(x) <= 0}
zl = 1 -> {x <= lb}

zu = 1 -> {F(x) >= 0}
zu = 1 -> {x >= ub}

zint = 1 -> {F(x) == 0}
zl + zu + zint == 1

(F2)

(zl,zu,zbound) in {0,1}
x in Interval(lb, ub)

zl = 1 -> {F(x) <= 0}
zl = 1 -> {x <= lb}

zu = 1 -> {F(x) >= 0}
zu = 1 -> {x >= ub}

zbound = 0 -> {F(x) == 0}
zbound >= zl
zbound >= zu

I think zl + zu + zint == 1 will convert the equality into two inequalities at the solver level (when running the simplex), so not sure the number of constraints vary. On the other hand, some solvers do not support activate on zero.

[odow]

The issue at present is that bridges handle constraints on a case-by-case basis. This requires bridges to be able to "see" multiple constraints: the complementarity constraint and the variable bounds.

The answer is probably to write a solver wrapper like https://github.com/chkwon/Complementarity.jl/blob/master/src/mpec.jl, which does different reformulations.

model = Model(() -> Complementarity.Optimizer(Gurobi.Optimizer, method = Complementarity.Indicator()))
@variable(model, x)
@constraint(model, [2x, x] in MOI.Complements(1))
optimize!(model)

You could also do the Fisher-Burmeister

model = Model(() -> Complementarity.Optimizer(Ipopt.Optimizer, method = Complementarity.FisherBurmeister()))
@variable(model, x)
@constraint(model, [2x, x] in MOI.Complements(1))
optimize!(model)

[odow]

I'm settling on the idea of "model transforms", which are solvers which wrap other solvers and provide model-level reformulations. A good example is Dualization.Optimizier.

You could nest these, so that you get something like:

Model(
    () -> JuMP.ConicPresolve(Dualization.Optimizer(SCS.Optimizer()))
)

Take a JuMP model, presolve it, then take the dual, then solve with SCS.

[matbesancon]

Closing this for now, let's see if we can come up with an alternative solution to bridges for this