Strong vs. Weak Formulations of the Same MIP

Two formulations of the same MIP share the same integer feasible set but may have very different LP relaxation polyhedra. A formulation is stronger when its LP relaxation is contained in the other's, giving a tighter LP bound and faster branch-and-bound. Common sources of weakness include loose big-M constants and aggregated linking constraints; their tight or disaggregated counterparts are strictly stronger.

Step 1 of 157%

Tutorial

Two Formulations of the Same MIP

A mixed integer program (MIP) typically admits many algebraically distinct descriptions that share the same integer feasible set $S$ . Two such descriptions are called different formulations of the same MIP.

Given two formulations $A$ and $B$ , let $P_A$ and $P_B$ denote the polyhedra obtained by dropping the integrality constraints -- the LP relaxation feasible regions. Both must satisfy $P_A \cap \mathbb{Z}^n = P_B \cap \mathbb{Z}^n = S$ .

Formulation $A$ is at least as strong as $B$ if

P_A \subseteq P_B.

If the containment is strict ( $P_A \subsetneq P_B$ ), then $A$ is strictly stronger than $B$ .

Geometrically, the stronger formulation wraps more tightly around the integer points of $S$ . The strongest possible formulation has $P = \operatorname{conv}(S)$ , the convex hull of $S$ .

For a tiny example, the integer set $S = \{0, 1, 2\}$ admits the formulations

A:\ 0 \leq x \leq 2,\ x \in \mathbb{Z}, \qquad B:\ 0 \leq x \leq 2.7,\ x \in \mathbb{Z}.

Both have integer points $\{0, 1, 2\}$ , but $P_A = [0, 2] \subsetneq [0, 2.7] = P_B$ . So $A$ is strictly stronger.