Extended Formulations: Trading Variables for Tightness

An ideal formulation for $S \subseteq \mathbb{Z}^n$ describes $\operatorname{conv}(S)$ with linear inequalities -- so the LP relaxation already solves the IP. The catch is size: classical integer sets can require an enormous (often exponential) number of inequalities to describe in the original $x$-space.

The way out is to introduce extra auxiliary variables. A polyhedron that takes many inequalities to describe in $\mathbb{R}^n$ may be the shadow of a much simpler polyhedron living in $\mathbb{R}^{n+k}$.

An extended formulation of a polyhedron $P \subseteq \mathbb{R}^n$ is a polyhedron $Q \subseteq \mathbb{R}^{n+k}$ such that

$$P \;=\; \operatorname{proj}_x(Q) \;:=\; \{x \in \mathbb{R}^n : \exists\, w \in \mathbb{R}^k \text{ with } (x, w) \in Q\}.$$

The extra coordinates $w_1, \ldots, w_k$ are called auxiliary variables. They do not appear in the original objective; they exist only to make the description of $P$ smaller or tighter, and they get projected out before the original problem is read off.

To project $Q$ onto $x$, we eliminate $w$: keep a point $x$ exactly when some $w$ makes $(x, w)$ feasible. Concretely, let

$$Q = \{(x, w) \in \mathbb{R}^2 : 0 \le w \le 1,\ w \ge x,\ w \ge -x\}.$$

For each $x$, a feasible $w$ must satisfy $\max(x, -x, 0) \le w \le 1$. Such a $w$ exists iff $|x| \le 1$, so

$$\operatorname{proj}_x(Q) = [-1, 1].$$

The variable $w$ acted as a stand-in for $|x|$, but the resulting description of $P$ in $x$-space is purely linear.