Ideal Formulations and the Convex Hull

Defines the convex hull of an integer feasible set and the notion of an ideal formulation (one whose LP relaxation equals the convex hull). Compares formulation strength, shows how an ideal formulation makes the LP relaxation solve the IP, and reinforces the connection to disaggregated constraints.

Step 1 of 157%

Tutorial

The Convex Hull and Ideal Formulations

Given an integer set $S \subseteq \mathbb{Z}^n,$ we usually optimize over $S$ by writing an LP relaxation

P = \{\mathbf{x}\in\mathbb{R}^n : A\mathbf{x}\le\mathbf{b}\},\qquad P\cap\mathbb{Z}^n = S.

The relaxation contains every integer point of $S$ but typically many fractional points as well. The fewer fractional extras, the tighter the bound the LP delivers.

The convex hull of $S,$ denoted $\operatorname{conv}(S),$ is the smallest convex set containing $S.$ For a finite $S=\{\mathbf{x}_1,\ldots,\mathbf{x}_k\},$ it consists of all convex combinations:

\operatorname{conv}(S) = \left\{\sum_{i=1}^k \lambda_i\mathbf{x}_i \,:\, \lambda_i\ge 0,\ \sum_{i=1}^k \lambda_i = 1\right\}.

A formulation $P$ of $S$ is ideal if

P = \operatorname{conv}(S).

For example, consider $S=\{(0,0),(1,0),(0,1)\}.$ The convex hull is the triangle with these three vertices, described by

x\ge 0,\quad y\ge 0,\quad x+y\le 1.

These three inequalities form the ideal formulation of $S.$