Comparing LP Relaxations of Equivalent Formulations

Two formulations of a mixed-integer program (MIP) are equivalent when they produce the same set of integer-feasible points. Their LP relaxations -- obtained by dropping integrality -- need not coincide.

Let $P_A$ and $P_B$ denote the LP feasible regions of two equivalent formulations $A$ and $B$. Formulation $A$ is at least as strong as $B$ when

$$P_A \subseteq P_B.$$

If in addition $P_A \neq P_B$, we say $A$ is strictly stronger than $B$.

To prove $P_A \subseteq P_B$, show every constraint of $B$ is implied by the constraints of $A$. To prove strictness, exhibit a fractional point in $P_B \setminus P_A$.

For example, take $x \in [0,3]$, $y \in \{0,1\}$, with $x = 0$ required when $y = 0$. Compare

$$\text{(A): } x \le 3y, \qquad \text{(B): } x \le 5y.$$

If $x \le 3y$ holds, then $x \le 3y \le 5y$ (since $y \ge 0$), so $P_A \subseteq P_B$. The point $(x,y) = (3, 0.7)$ satisfies $3 \le 5(0.7) = 3.5$ but fails $3 \le 3(0.7) = 2.1$, so $(3, 0.7) \in P_B \setminus P_A$. Therefore $A$ is strictly stronger than $B$.