The Integer Hull and the Integrality Gap

Let $P$ denote the feasible region of the LP relaxation of an IP. Every integer feasible point lies in $P,$ but $P$ also contains fractional points that violate the integrality requirement.

The integer hull of the IP, denoted $P_I,$ is the convex hull of the integer feasible points:

$$P_I = \mathrm{conv}\bigl(P \cap \mathbb{Z}^n\bigr).$$

Since every integer feasible point lies in $P,$ we have

$$P_I \subseteq P.$$

Key property. Maximizing or minimizing a linear objective over $P_I$ yields the same optimal value as the original IP. If we could write the inequalities defining $P_I$ explicitly, we could solve the IP by solving an LP over $P_I.$

Mini-example. Consider $x_1 + x_2 \le 2.5,\ x_1, x_2 \ge 0,\ x_1, x_2 \in \mathbb{Z}.$ The integer feasible points are

$$(0,0),\ (1,0),\ (2,0),\ (0,1),\ (1,1),\ (0,2).$$

Their convex hull is the triangle with vertices $(0,0),\ (2,0),\ (0,2),$ described by

$$x_1 + x_2 \le 2,\quad x_1 \ge 0,\quad x_2 \ge 0.$$

The integer hull has the tighter constraint $x_1 + x_2 \le 2$ in place of the LP's $x_1 + x_2 \le 2.5.$

In general, finding $P_I$ is hard. But conceptually it captures exactly the information needed to solve the IP.