Integer Programs
An Integer Program (IP) is an optimization problem in which the objective function and constraints are affine, as in a linear program, but some or all decision variables are restricted to take integer values. A common binary formulation is
\min_{x \in \mathbb{R}^n} \quad & a_0^\top x \\ \text{s.t.} \quad & Ax = b, \\ & Cx \le d, \\ & x_i \in \{ 0,1 \}, \quad i = 1,\dots,n. \end{aligned}$$ Without the integrality constraints, this problem is exactly a **linear program**, whose feasible set is a convex polyhedron formed by the intersection of hyperplanes and half-spaces. Imposing $x_i \in \{0,1\}$ restricts feasibility to a finite set of points inside that polyhedron, destroying convexity. As a result, integer programs are **not convex optimization problems**, and convex combinations of feasible solutions are generally infeasible. The standard way to analyze and solve integer programs is through their LP [[3.3. Convex Relaxation|relaxation]], obtained by replacing $x_{i} \in \{ 0, 1 \}$ with $0 \le x_{i} \le 1$. This relaxed problem is a linear program and therefore convex. Its optimal value provides a lower bound on the optimal value of the integer program. Geometrically, integer programs can be viewed as selecting discrete points from a polyhedron, while LP relaxations optimize over the entire polyhedron. This explains both why LPs are efficiently solvable and why IPs are generally NP-hard. Thus, integer programs are best understood as **linear programs with additional integrality structure**.
Examples
Vertex Cover as IP and Relaxation
Given an undirected graph with a cost function , the vertex cover problem asks us to find the minimum cost subset of vertices such that every edge in is incident on some vertex in that subset.
Formulate the vertex cover problem as an integer linear program.