One word — "integer" — changes everything.
Chapter: 0b — MIP theory · lesson id mip-what · theory lesson
A linear program with $continuous$ decision variables is solved in polynomial time and the algorithms have been engineered to within an inch of their life. Replace some of those variables with the constraint that they must be integers, and the problem becomes one of the canonical NP-hard problems. This lesson is what changes, why, and how the practical answer is "solve a relaxation and search around it".
Definition (Mixed-integer linear program (MIP, MILP)). Given $c \in \mathbb{R}^{n}$, $A \in \mathbb{R}^{m \times n}$, $b \in \mathbb{R}^{m}$, and a subset $I \subseteq {1, \ldots, n}$ of indices declared $integer$, a $mixed$-$integer\ linear\ program$ is $$\min_{x} c^{\top} x \quad \text{subject to} \quad A x \leq b, ; x_{j} \in \mathbb{Z} \text{ for } j \in I, ; x \geq 0.$$ If $I = {1, \ldots, n}$ (every variable is integer), it is a $pure$ integer program. If $I$ contains only $0/1$ variables, it is a $binary\ integer\ program$.
The change from LP to MIP looks tiny on paper — one word, "integer" — but it is the difference between $\text{P}$ and $\text{NP}$-hard.
Theorem (Complexity). The decision version of integer programming is $\text{NP}$-complete (Karp, 1972). Equivalently, integer linear feasibility cannot be solved in time polynomial in the input size unless $\text{P} = \text{NP}$.
Several familiar problems reduce to integer programming: $0$-$1$ knapsack, set cover, vertex cover, the travelling salesman problem. Conversely, anything you can write as a polynomial-size integer program inherits the same worst-case hardness. The good news is that "worst-case hard" is not "hopeless"; commercial MIP solvers routinely tame instances with millions of variables when the structure cooperates.
The Fundamental Theorem of LP (from the previous chapter) gave us a finite set of candidates to check: the vertices of a polyhedron. Integer constraints destroy that. The feasible set of a MIP is the polyhedron $P = {x : A x \leq b, x \geq 0}$ $intersected$ with the integer lattice $\mathbb{Z}^{n}$ on the chosen coordinates. The integer hull — the convex hull of those integer feasible points — is itself a polyhedron, but with potentially exponentially many vertices, and we have no fast way to enumerate them.
[feasible-region diagram: For max x₁ + x₂ in the shaded region, the LP optimum sits at the fractional vertex (12/7, 12/7) with Z = 24/7 ≈ 3.43. No integer feasible point reaches it — the best integer Z is 3, tied at (3,0), (0,3), (2,1), and (1,2). The LP optimum and the integer optimum genuinely differ.]
Quick check. For the LP $\max\ x_{1} + x_{2}$ subject to $x_{1} + x_{2} \leq 4.5$ and $x_{1}, x_{2} \geq 0$, what is the LP optimum and what is the integer optimum?
Recap.
Read this through MCP: read with path: "lessons/mip-what", or resource hlpl://lessons/mip-what.