Conditional Constraints Without Big-M

Encoding logical implications between binary variables as linear constraints without resorting to Big-M parameters. Covers simple implications, disjunctive consequents, conjunctive antecedents, and combined forms.

Step 1 of 157%

Tutorial

Implications Between Binary Variables

When all variables in an implication are binary ( $\{0,1\}$ -valued), we can encode the implication

x = 1 \;\Rightarrow\; y = 1

as a single linear inequality, with no Big-M parameter needed:

x \le y.

To verify: if $x = 1$ , then $y \ge 1$ , and since $y$ is binary we conclude $y = 1$ . If $x = 0$ , then $y \ge 0$ holds automatically, so the constraint imposes nothing.

For instance, suppose $a, b \in \{0,1\}$ and we want to enforce "if $a$ is chosen, then $b$ is chosen." We simply write

a \le b.

Contrast this with Big-M, where linking a binary indicator to a continuous variable requires a large constant $M$ . Here both sides are binary, so the tightest possible coefficient is $1$ — no Big-M is required, and the LP relaxation is as tight as it can be.