Integer Programming

Integer programming is the subfield of mathematical optimization in which some or all variables are constrained to take integer values. It is the discrete counterpart to linear programming, and the small change in constraint — whole numbers instead of real numbers — transforms a tractable problem into one that is, in general, NP-hard.\n\nThe canonical form is the mixed-integer linear program (MILP): minimize a linear objective subject to linear constraints, with some variables required to be integers. When all variables are integer, the problem is a pure integer program. When variables are restricted to 0 or 1, it is a binary integer program, the form used for most combinatorial problems: selecting edges, assigning tasks, choosing routes.\n\nThe standard solution approach is branch and bound: solve the linear relaxation, then recursively partition the search space by branching on fractional variables and bounding subproblems that cannot improve the incumbent. Modern solvers — CPLEX, Gurobi, SCIP — combine branch and bound with cutting plane methods that dynamically add constraints to tighten the relaxation.\n\nThe integrality gap — the ratio between the optimal integer solution and the optimal relaxed solution — measures how much the discrete constraint costs. When the gap is small, the problem is nearly convex. When it is large, the discrete structure dominates and exact solution becomes expensive.\n\nInteger programming is where the idealized mathematics of continuous optimization collides with the granular reality of indivisible things. The collision is expensive, but it is the only way to build networks, schedules, and systems that actually exist.\n\n\n\n