Indicator Constraints v. Big M

Written by: Paul Rubin

Primary Source: OR in an OB World, 6/10/2019.

Way, way back I did a couple of posts related to how to model “logical indicators” (true/false values that control enforcement of constraints):

The topic ties in to the general issue of “big M” model formulations. Somewhere around version 10, CPLEX introduced what they call indicator constraints, which are essentially implications of the form “if constraint 1 holds, then constraint 2 holds”. As an example, if \(a\) and \(b\) are vector respectively scalar parameters, \(x\) is a binary variable and \(y\) is a vector of real variables, you might use an indicator constraint to express \(x=1 \implies a’y\le b\).

That same constraint, in a “big M” formulation, would look like \(a’y \le b + M(1-x)\). Using an indicator constraint saves you having to make a careful choice of the value of \(M\) and avoids certain numerical complications. So should you always use indicator constraints? It’s not that simple. Although “big M” formulations are notorious for having weak relaxations, indicator constraints can also result in weak (possibly weaker) relaxations.

For more details, I’ll refer you to a question on the new Operations Research Stack Exchange site, and in particular to an answer containing information provided by Dr. Ed Klotz of IBM. My take is that this remains one of those “try it and see” kinds of questions.

The following two tabs change content below.
I'm an apostate mathematician, retired from a business school after 33 years of teaching mostly (but not exclusively) quantitative methods courses. My academic interests lie in operations research. I also study Tae Kwon Do a bit on the side.

Latest posts by Paul Rubin (see all)