Indicator and SOS to MILP bridges

[odow]

I talked to @fdabrandao (AMPL) at INFORMS. They have a lot of new stuff for reformulating indicator constraints to MILP. We can't offer the same full flexibility as AMPL, but we could write a few XXXtoMILPBridges, just like we've done for constraint programming.

In all cases, M is based on bounds of x, and we error if bounds are not present.

• z --> {a'x <= b} => a'x <= b + M(1 - z)
• !z --> {a'x <= b} => a'x <= b + Mz
• z --> {a'x >= b} => a'x >= b - M(1 - z)
• !z --> {a'x >= b} => a'x >= b - Mz
• z --> {a'x == b} => a'x == b + y, -M(1-z) <= y <= M(1 - z)
• !z --> {a'x == b} => a'x == b + y, -Mz <= y <= Mz
• x in SOS1 => -l_i z_i <= x_i <= u_i z_i, sum z_i == 1
• x in SOS2 => -l_i (z_i+z_j) <= x_i <= u_i (z_i + z_j), sum z_i == 1

cc @glebbelov

[odow]

We have IndicatorSOS1Bridge:

MathOptInterface.jl/src/Bridges/Constraint/bridges/indicator_sos.jl

Lines 7 to 33 in d9417ae

	"""
	IndicatorSOS1Bridge{T,S} <: Bridges.Constraint.AbstractBridge
	`IndicatorSOS1Bridge` implements the following reformulation:
	* ``z \\implies {f(x) \\in S}`` into ``f(x) + y \\in S``,
	``SOS1(y, z)``
	!!! warning
	This bridge assumes that the solver supports [`MOI.SOS1{T}`](@ref)
	constraints in which one of the variables (``y``) is continuous.
	## Source node
	`IndicatorSOS1Bridge` supports:
	* [`MOI.VectorAffineFunction{T}`](@ref) in
	[`MOI.Indicator{MOI.ACTIVATE_ON_ONE,S}`](@ref)
	## Target nodes
	`IndicatorSOS1Bridge` creates:
	* [`MOI.ScalarAffineFunction{T}`](@ref) in `S`
	* [`MOI.VectorOfVariables`](@ref) in [`MOI.SOS1{T}`](@ref)
	"""
	struct IndicatorSOS1Bridge{T,S<:MOI.AbstractScalarSet} <: AbstractBridge

So it might be sufficient to have SOS1ToMILPBridge, and then optionally add bounds to the slack indicator variable if possible.

[odow]

Ah, but this would need final_touch, and so would SOS1toMILPBridge, which would require #1980

[odow]

Closed by #2318