Integer Programming (IP)

Integer programming (pure IP) is the problem class min c^T x s.t. Ax ≤ b, x ∈ Z^n_+ in canonical form, in which every decision variable is integer. The 0-1 (binary) special case x ∈ {0,1}^n is the natural formulation for combinatorial optimization: knapsack, assignment, set covering, set partitioning, the traveling salesman problem (TSP), matching, and graph coloring. Complexity: pure IP appears as 0-1 IP in Karp's (1972) list of 21 NP-complete problems; Lenstra (1983) showed IP is polynomial-time solvable in fixed dimension (impractical when dimension is part of the input). When integrality is imposed on the LP relaxation, the optimum value can shift sharply; the integrality gap is the canonical measure of formulation strength. The classic algorithm is Gomory's (1958) cutting-plane method: solve the LP relaxation, if the optimum is fractional generate a Gomory cut (using simplex tableau information) that excludes the current LP optimum but no integer feasible point, add it, and re-solve; this terminates at an integer optimum in finitely many iterations (in theory). In practice Land and Doig's (1960) branch-and-bound, later branch-and-cut (Padberg and Rinaldi 1991), is faster. Polyhedral theory — Chvátal (1973), Schrijver (1986) — derives valid inequalities (subtour-elimination and blossom inequalities for TSP) that tighten the LP relaxation to approach the convex hull of integer feasible points. Practical applications: TSP / vehicle routing (Dantzig, Fulkerson, and Johnson 1954), assignment, scheduling, network flow, cutting stock (Gilmore and Gomory 1961), bin packing.