Disjunctive Constraints via Big-M

A disjunctive constraint requires that at least one of two linear constraints hold. A pure linear program only expresses conjunctions (every constraint must hold simultaneously), so a disjunction like

$$f_1(\mathbf{x}) \leq b_1 \quad \text{OR} \quad f_2(\mathbf{x}) \leq b_2$$

cannot be encoded directly. We introduce a binary indicator $y \in \{0,1\}$ and large constants $M_1, M_2 \geq 0$ that relax whichever constraint is deactivated:

$$f_1(\mathbf{x}) \leq b_1 + M_1(1-y)$$ $$f_2(\mathbf{x}) \leq b_2 + M_2 y$$ $$y \in \{0,1\}$$

The indicator $y$ selects which constraint is active:

• When $y = 1$: the first reduces to $f_1(\mathbf{x}) \leq b_1$ (active); the second becomes $f_2(\mathbf{x}) \leq b_2 + M_2$, which is redundant for $M_2$ large enough.
• When $y = 0$: the first is relaxed to $f_1(\mathbf{x}) \leq b_1 + M_1$; the second, $f_2(\mathbf{x}) \leq b_2$, is enforced.

In either case, at least one of the original constraints holds.

For example, to enforce $x_1 + x_2 \leq 4$ OR $x_1 - x_2 \leq 1$, we write

$$x_1 + x_2 \leq 4 + M_1(1-y)$$ $$x_1 - x_2 \leq 1 + M_2 y$$ $$y \in \{0,1\}.$$