What Is Integer Linear Programming?

Integer linear programming (ILP) is a mathematical optimization framework in which the objective function and all constraints are linear, but some or all decision variables are required to take integer values rather than continuous values. When all variables must be integers, the problem is called a pure integer program; when only a subset must be integers, it is a mixed-integer linear program (MILP). ILP is a branch of mathematical programming that sits at the intersection of linear algebra, combinatorics, and computational complexity theory. It provides a rigorous formulation language for scheduling, resource allocation, network design, and combinatorial optimization problems that arise throughout engineering and operations research.

The discipline traces its origins to the work of Ralph Gomory in the late 1950s, who introduced the cutting plane method for solving integer programs, and to the branch-and-bound framework developed independently by Land and Doig in 1960. These two algorithmic ideas remain the foundation of every modern commercial ILP solver, including CPLEX, Gurobi, and the open-source GLPK and SCIP packages.

Problem Formulation and LP Relaxation

An ILP instance specifies a vector of decision variables, a linear objective function to minimize or maximize, and a set of linear inequality and equality constraints. Integrality requirements are imposed on some or all variables. The LP relaxation of an ILP drops the integrality constraints and solves the resulting continuous linear program, which can be done in polynomial time. The optimal value of the LP relaxation is a bound on the ILP optimum: for minimization problems, the relaxation value is always less than or equal to the integer optimum. The gap between these two values, the integrality gap, measures how much work the integrality constraints add beyond the continuous case. A tight LP relaxation with a small integrality gap greatly reduces the computational effort required to solve the integer problem.

Branch-and-Bound and Cutting Plane Methods

The branch-and-bound algorithm solves an ILP by first solving the LP relaxation. If any variable has a fractional value in the LP solution, the algorithm branches: it creates two subproblems by adding floor and ceiling constraints on that variable, partitioning the feasible region. Each subproblem is a new LP relaxation that is solved recursively. Bounds from already-solved subproblems are used to prune branches whose LP relaxation values cannot improve on the current best integer solution. The cutting plane method, developed by Gomory, takes a different approach: it adds valid linear inequalities (cuts) to the original LP that remove the fractional LP optimal solution without cutting off any integer feasible point, tightening the relaxation toward the integer hull. Research published on arxiv analyzing the complexity of branch-and-bound and cutting planes in mixed-integer optimization establishes theoretical results on the relative power of these methods, demonstrating that their combination in branch-and-cut algorithms can achieve exponential improvements over either method used alone. The branch-and-cut framework in practice combines strong cutting planes generated at each node of the branch-and-bound tree with sophisticated variable selection heuristics, making modern solvers capable of handling instances with millions of variables and constraints.

Computational Complexity and Solver Technology

ILP is NP-hard in general, meaning no polynomial-time algorithm is known to solve all instances. Despite this worst-case characterization, practical ILP solvers exploit problem structure, preprocessing routines, and dual information to solve large real-world instances routinely. Warm-starting from a good feasible solution and using primal heuristics to find integer solutions early in the search tree are standard techniques.

Applications

Integer linear programming has applications across a wide range of technical and economic fields, including:

• Network flow and routing optimization in telecommunications
• Production scheduling and supply chain planning in manufacturing
• Crew and vehicle scheduling for transportation and logistics
• Power grid unit commitment and optimal dispatch in energy systems
• Circuit placement and routing in VLSI chip design
• Combinatorial assignment problems in wireless spectrum allocation