Integer Linear Programming

Interactive visualizations for Chapter 3 of the Ricerca Operativa notes

LP Relaxation vs ILP Feasible Region

An Integer Linear Program (ILP) adds integrality constraints to an LP. The key insight is that the feasible region of an ILP is not a continuous polyhedron — it is a finite set of lattice points (integer-coordinate points) inside a polyhedron.

We work with the following 2D ILP:

\[ \begin{aligned} & \text{maximize} && 3\,x_1 + 5\,x_2 \\ & \text{subject to} && x_1 \leq 4 \\ & && 2\,x_2 \leq 12 \\ & && 3\,x_1 + 5\,x_2 \leq 25 \\ & && x_1, x_2 \geq 0, \quad x_1, x_2 \in \mathbb{Z}. \end{aligned} \]

• The LP relaxation (dropping integrality) has a continuous feasible region shaded in light blue.
• Green dots are integer lattice points that satisfy all constraints (ILP-feasible).
• Gray dots are integer lattice points that violate at least one constraint (ILP-infeasible).
• The LP optimum (star, orange) is the continuous optimum — possibly non-integer.
• The ILP optimum (star, purple) is the best integer-valued solution.
• The gap between the two objective values is the integrality gap.

viewof b3 = Inputs.range([20, 30], {value: 25, step: 1, label: "Termine Noto Diagonale (b3):"})

The LP relaxation optimum lies on the edge between \((0, 5)\) and \((4, 2.6)\) — both vertices give \(z = 25\). The best integer solution is \((0, 5)\) with \(z^* = 25\), so in this instance the integrality gap is exactly \(1\) (the LP optimum happens to be integer). Change the RHS of the diagonal constraint to see a nonzero gap.

---

Strong vs Weak Formulations

The same ILP can be described by different LP relaxations. A weak formulation has a large LP relaxation polytope (loose constraints); a strong formulation has a smaller polytope (tight constraints closer to the integer hull). Both describe the same set of integer feasible points, but stronger formulations give tighter bounds and solve faster.

We compare two formulations for a simple knapsack-style ILP with \(x_1, x_2 \in \{0,1\}\):

• Weak formulation: use only the natural bounds \(0 \leq x_i \leq 1\) plus the packing constraint. The LP relaxation is the unit square intersected with the half-plane.
• Strong formulation: add the additional valid inequality \(x_1 + x_2 \leq 1\) (at most one item), which cuts off the fractional region significantly.

Specifically, the problem is:

\[ \begin{aligned} & \text{maximize} && 5\,x_1 + 4\,x_2 \\ & \text{subject to} && 3\,x_1 + 2\,x_2 \leq 4, \quad x_1, x_2 \in \{0,1\}. \end{aligned} \]

The integer feasible points are \(\{(0,0),\,(0,1),\,(1,0)\}\) — note \((1,1)\) violates the constraint since \(3+2=5>4\).

Left (weak): The LP relaxation polytope \(P_{\mathrm{weak}}\) includes fractional points such as \((1, 0.5)\), giving \(z_{\mathrm{LP}} = 7.0\) — strictly above the ILP optimum \(z^*_{\mathrm{ILP}} = 5\). Right (strong): Adding the valid inequality \(x_1 + x_2 \leq 1\) cuts off all fractional interior points and the LP optimum coincides with the ILP optimum. A stronger formulation closes the integrality gap.

---

Convex Hull: The Ideal Formulation

The convex hull \(\operatorname{conv}(X)\) of the integer feasible set \(X\) is the smallest convex set containing all ILP feasible points. If we could describe this convex hull explicitly as a polyhedron, the LP over that polyhedron would give the ILP optimum directly — no branch-and-bound needed. This is the ideal formulation.

In practice, the convex hull description typically requires exponentially many inequalities (it is NP-hard to compute in general). But for small instances we can visualize it.

We use the ILP:

\[ \begin{aligned} & \text{maximize} && x_1 + 3\,x_2 \\ & \text{subject to} && x_1 + x_2 \leq 4.5 \\ & && x_1 \leq 3 \\ & && x_2 \leq 4 \\ & && x_1, x_2 \geq 0, \quad x_1, x_2 \in \mathbb{Z}. \end{aligned} \]

viewof b_ch = Inputs.range([3.0, 5.0], {value: 4.5, step: 0.1, label: "RHS Vincolo x1 + x2 <= b_ch:"})

Left: The LP relaxation polytope \(P\) extends beyond the integer hull. Its optimum \((0.5, 4)\) gives \(z_{\mathrm{LP}}^* = 0.5 + 3\cdot4 = 12.5\), which is not attained by any integer point. Right: The convex hull \(\operatorname{conv}(X)\) is the tightest possible polyhedron containing exactly the integer feasible points. Its LP optimum coincides with the ILP optimum \((0, 4)\), \(z^* = 12\), with no integrality gap. This is the ideal formulation — but in general it requires exponentially many inequalities to describe.