Integer Programming — Mathematics Knowledge System

Overview

Integer programming (IP) is a class of mathematical optimization problems in which some or all decision variables are required to take integer values. When all variables must be integers it is called pure integer programming; when only some must be, it is mixed-integer programming (MIP). Despite the apparent similarity to linear programming, the integrality constraint makes IP NP-hard in general. Techniques such as branch-and-bound, cutting planes, and LP relaxations form the algorithmic backbone of modern IP solvers.

Intuition

An LP relaxation of an IP is obtained by dropping the integrality constraints. The LP relaxation is easy to solve and provides a bound on the optimal integer value. Branch-and-bound exploits this: solve the LP relaxation, and if the solution is not integral, branch on a fractional variable (creating two subproblems by rounding up and down), pruning branches whose LP bound cannot improve the best integer solution found so far.

Formal Definition

Definition

A pure integer program in standard form minimizes a linear objective over integer vectors satisfying linear constraints.

\min_{x \in \mathbb{Z}^n} c^T x \quad \text{subject to} \quad Ax \leq b,\quad x \geq 0

Pure integer program

\min_{x,y} c^T x + d^T y \quad \text{subject to} \quad Ax + By \leq b,\quad x \in \mathbb{Z}^p,\; y \in \mathbb{R}^q,\; x,y \geq 0

Mixed-integer program (MIP)

\text{LP relaxation: drop } x \in \mathbb{Z}^n \text{, replace with } x \in \mathbb{R}^n

LP relaxation

Notation

Notation	Meaning
$\text{IP}$	Integer program
$\text{MIP}$	Mixed-integer program
$z^*$	Optimal integer objective value
$z_{\mathrm{LP}}$	LP relaxation optimal value (a lower bound for minimization)

Theorems

Theorem 1: Integrality of LP over TDI Systems

\text{If } A \text{ is totally unimodular and } b \in \mathbb{Z}^m, \text{ the LP } \min\{c^T x : Ax \leq b, x \geq 0\} \text{ has an integer optimal solution}

Theorem 2: Gomory's Cutting Plane Theorem

\text{Any rational IP has a finite sequence of Gomory cuts that leads to an integer optimal solution}

Theorem 3: NP-hardness of Integer Programming

\text{Integer linear programming is NP-complete (even for 0-1 variables)}

Worked Examples

1
The LP relaxation gives optimal at (5, 0) or along the edge — objective 25.
$\max 5x + 4y,\quad x + y \leq 5,\quad x,y \geq 0$
2
Since the LP optimal (5, 0) is already integer, it is also the IP optimal.
$x^* = 5,\; y^* = 0,\; z^* = 25$

✓ Answer

Optimal IP solution: x = 5, y = 0, objective = 25.

Practice Problems

Mediumfree response

Formulate the 0-1 knapsack problem as an integer program.

Hardproof writing

Show that the LP relaxation of an IP provides a lower bound on the optimal IP objective (minimization).

Common Mistakes

Common Mistake

Rounding the LP relaxation solution always gives a feasible integer solution

Rounding can violate constraints. Branch-and-bound or cutting planes are needed to find the true integer optimum.

Common Mistake

Integer programming is just slightly harder than LP

IP is NP-hard; LP is polynomial. The integrality constraint causes an exponential blowup in worst-case complexity.

Quiz

Which algorithmic approach solves an IP by recursively partitioning the feasible set and solving LP relaxations?

Simplex methodGradient descentBranch-and-boundEllipsoid method

A totally unimodular constraint matrix guarantees what property of the LP relaxation?

Zero duality gapInteger optimal vertex for integer RHSUnique optimal solutionPolynomial-time solvability only

Historical Background

Integer programming arose from practical scheduling and combinatorial problems in the 1950s. Ralph Gomory introduced the cutting-plane method in 1958, providing the first systematic exact algorithm. Branch-and-bound was formalised by Land and Doig in 1960. The field was unified and deepened by Nemhauser and Wolsey's landmark 1988 textbook, which remains the standard reference.

1958
Gomory introduces the cutting-plane (Gomory cut) method for integer programs
Ralph Gomory
1960
Land and Doig formalise the branch-and-bound algorithm
Ailsa Land, Alison Doig
1979
Integer programming proved NP-hard via reduction from satisfiability
1988
Nemhauser and Wolsey publish 'Integer and Combinatorial Optimization'
George Nemhauser, Laurence Wolsey

Summary

Integer programming requires some or all variables to be integers, making it NP-hard in general.
The LP relaxation provides a bound; the integrality gap measures how far it is from the true optimum.
Branch-and-bound systematically searches the integer feasible set using LP bounds to prune.
Gomory cuts and other cutting-plane families tighten the LP relaxation toward the integer hull.
Totally unimodular matrices guarantee integer LP optima, explaining why network flow problems solve easily.

References

BookNemhauser, G.L. & Wolsey, L.A. — Integer and Combinatorial Optimization (1988), Wiley
BookSchrijver, A. — Theory of Linear and Integer Programming (1986), Wiley
BookWolsey, L.A. — Integer Programming (1998), Wiley
WebsiteWikipedia — Integer programming
WebsiteMathWorld — Integer Programming