Difference between using indicator constraints and a big-M formulation

Answer

CPLEX 10 introduced indicator constraints as an alternative to big-M formulations.

Both of these constructions typically use a binary variable to turn on or turn off the enforcement of a constraint, or to relate a binary variable to a continuous variable or expression.

For example, to express this idea:

if z = 0, then x = 0
where z binary, and x >= 0

we could use the big-M formulation:

x - M * z <= 0

or the indicator constraint formulation:

z = 0 -> x = 0

Big-M formulations are relatively straightforward, but the value of the M term needs to be chosen carefully. If M is smaller than the upper bound of x, this situation may cut off valid solutions. If M is too large, the model may become numerically difficult or exhibit trickle flow.

Indicator constraints have the advantage of avoiding these types of problems, as they do not rely on a separate constant value. However, they tend to have weaker relaxations during the MIP optimization, a condition which may lead to longer solve times in a model.

Consider using the big-M form instead of indicators:

• When the big-M factor is not much larger than other coefficients in the model.
• If the big-M factor is eliminated in presolve. You can write out the presolved model to check this condition.
• If the model does not show any side effects from a big-M formulation.
• If neither CPLEX 10.0 nor 10.1 can efficiently solve the model formulated with indicator constraints.

Consider using indicator constraints instead of big-M:

• When the big-M factor remains very large, relative to other coefficients in the model.
• When the big-M formulation is difficult to express, such as an if-then constraint on complex expressions.

In all cases, defining upper bound information on the continuous variable will generally yield a much tighter formulation and nearly always helps with performance.

With Concert and CPLEX 10, the default formulation of linearized operators, like IloIfThen, IloAbs, and IloOr, involve indicator constraints. However, you can always write your own big-M formulation, if you wish.

For more information about indicator constraints, see the "Using Indicator Constraints" chapter of the CPLEX user's manual.