Question & Answer
Question
What is the 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.
Historical Number
cplex/FAQ/167
Was this topic helpful?
Document Information
Modified date:
16 June 2018
UID
swg21400084