Big-M Constraints: Linking Binary to Continuous Variables

How to use a Big-M coefficient to make a binary indicator variable switch a continuous decision variable on or off in an integer program. Covers the basic linking constraint x ≤ My, choosing the tightest valid M, forcing a minimum activity level when the indicator is on, and combining lower and upper linking constraints.

Step 1 of 157%

Tutorial

The Big-M Linking Constraint

In integer programming, a binary indicator $y \in \{0,1\}$ often controls whether a continuous variable $x \ge 0$ is allowed to take a positive value at all. We want

$y = 0 \,\Longrightarrow\, x = 0,$
$y = 1 \,\Longrightarrow\, x$ may take any value up to its natural upper bound.

A single linear inequality accomplishes this. If $M$ is a constant at least as large as the largest possible value of $x,$ then the Big-M linking constraint

x \le M y

does the job:

When $y = 0{:}$ the constraint becomes $x \le 0.$ Combined with $x \ge 0,$ this forces $x = 0.$
When $y = 1{:}$ the constraint becomes $x \le M,$ which is exactly the natural upper bound on $x.$

For example, if a factory can produce at most $200$ units when running, set $M = 200$ and write $x \le 200 y.$ With $y = 0$ the factory produces nothing; with $y = 1$ it may produce anywhere from $0$ to $200$ units.