What Is Integer Programming?

Integer programming (IP) is a class of mathematical optimization in which some or all decision variables are constrained to take integer values, as opposed to the continuous variables permitted in standard linear or nonlinear programming. The objective function and constraints may be linear, giving rise to integer linear programming (ILP) or mixed-integer linear programming (MILP), or they may involve nonlinear terms, yielding mixed-integer nonlinear programs (MINLPs). The integrality requirement introduces combinatorial structure that makes integer programs fundamentally harder to solve than their continuous relaxations, but it also makes the framework well suited to modeling decisions that are discrete by nature: whether to build a facility, how many units to produce, which nodes to include in a network.

Integer programming draws on combinatorics, linear algebra, polyhedral theory, and computational complexity. The field took shape in the late 1950s and early 1960s, with landmark contributions from Ralph Gomory (cutting plane method, 1958), Land and Doig (branch-and-bound, 1960), and subsequent work establishing the NP-hardness of the general integer programming problem. Research on its computational boundaries continues to inform algorithm design in solvers that are widely used in industry and academia.

Mixed-Integer and Binary Programming

A pure integer program requires all variables to be integers. A mixed-integer program partitions variables into a continuous set and an integer set. Binary programming is the special case where the integer variables are restricted to the set {0, 1}, encoding yes-or-no decisions. Binary programs arise naturally in assignment, covering, and facility location problems, where variables indicate whether a resource is assigned or a site is selected. The binary structure of a variable is exploited by solvers through specialized branching rules and presolve techniques that fix variable bounds before the main search begins. Quadratic binary programs, which arise in graph partitioning and portfolio selection, connect integer programming to semidefinite programming through relaxation hierarchies.

Solution Algorithms

The dominant algorithmic framework for solving integer and mixed-integer programs combines branch-and-bound search with cutting planes in what practitioners call branch-and-cut. In branch-and-bound, the algorithm solves LP relaxations and recursively partitions the feasible region by branching on fractional integer variables. Cutting plane methods, pioneered by Gomory's seminal 1958 work, add linear inequalities that tighten the LP relaxation without eliminating integer feasible solutions. Modern solvers combine thousands of classes of cutting planes, primal heuristics for finding good integer solutions early in the search, and preprocessing routines that reduce problem size before branching. Research published on the complexity of branch-and-bound and cutting planes in mixed-integer optimization provides theoretical foundations for understanding when each method confers an advantage. For nonlinear integer programs, outer approximation and Benders decomposition are common strategies that iteratively solve alternating continuous nonlinear and integer linear subproblems.

Computational Complexity and Practical Solvers

Integer programming is NP-hard in general, and many specific sub-problems are also NP-hard, including the traveling salesman problem, the knapsack problem, and the set cover problem. Despite this, commercial solvers such as CPLEX and Gurobi can solve instances with hundreds of thousands of integer variables by exploiting problem-specific structure and modern hardware. Benchmark studies published by the MIPLIB project document solver performance across diverse real-world mixed-integer linear instances, providing a standard basis for comparing algorithmic improvements. The INFORMS journal on computing regularly publishes advances in integer programming algorithms and their computational evaluation.

Applications

Integer programming has applications across a wide range of technical, economic, and scientific domains, including:

• Airline crew and fleet scheduling with binary assignment variables
• Telecommunications network design and routing with capacity constraints
• Power system unit commitment and generation scheduling
• Protein structure prediction and computational biology
• Vehicle routing and logistics with time windows
• Facility location and warehouse network design in supply chains