Integer programming

Integer programming is the study of optimization problems in which some or all decision variables are restricted to integer values. When every variable is integral, the model is an integer linear program; when integral and continuous variables occur together, it is a mixed-integer linear program. A binary integer program further restricts designated variables to the set ({0,1}), allowing them to represent logically indivisible decisions.

The standard linear form is

[ \begin{aligned} \text{minimize}\quad & c^\mathsf{T}x\ \text{subject to}\quad & Ax \le b,\ & x_i\in\mathbb Z \qquad i\in I, \end{aligned} ]

where (A), (b), and (c) contain rational data, while (I) identifies the components subject to integrality. Variables outside (I) are generally continuous. The corresponding linear programming relaxation removes the integrality restrictions and replaces them with ordinary real-valued bounds.

Integer programming is distinct from continuous optimization because integrality changes both the geometry and computational structure of a model. A linear program searches a convex polyhedron, whereas an integer program searches the lattice points contained within that polyhedron. Consequently, an optimum of the relaxation can lie at a fractional point that has no admissible interpretation in the original problem. A transport model, for example, may assign (2.4) vehicles under continuous relaxation even when the physical system provides neither four-tenths of a vehicle nor a separate use for its fractional axle inventory.

Mathematical structure

For a pure integer program, the feasible set is

[ P\cap\mathbb Z^n, \qquad P={x\in\mathbb R^n:Ax\le b}. ]

The convex hull of these feasible lattice points,

[ P_I=\operatorname{conv}(P\cap\mathbb Z^n), ]

is called the integer hull. Optimizing a linear objective over (P_I) is equivalent to optimizing it over the original integer points. The difficulty lies in obtaining a useful description of (P_I), since it can require many inequalities even when (P) has a compact formulation.

The value of the linear relaxation provides a lower bound for a minimization problem and an upper bound for a maximization problem. The difference between the relaxation value and the integer optimum is the integrality gap. This gap is a property of the formulation as well as of the underlying combinatorial problem: two formulations can encode the same admissible decisions while producing substantially different relaxations.

Some coefficient matrices make integrality automatic. If (A) is totally unimodular and (b) is integral, every vertex of the polyhedron ({x:Ax\le b}) is integral under the standard associated conditions. Network-flow formulations frequently have this property, which explains why several apparently discrete flow problems can be solved as linear programs. The property does not extend to arbitrary side constraints; a single additional coupling inequality can destroy total unimodularity and reintroduce fractional vertices.

Binary variables express logical structure through linear inequalities. For example, the relation (x\le y), with (x,y\in{0,1}), states that selecting (x) requires selecting (y). More elaborate disjunctions can be represented through extended formulations containing auxiliary variables. Such representations preserve linearity while transferring logical complexity into the geometry of a higher-dimensional polyhedron.

Historical development

Early foundations arose from mathematical treatments of allocation and production. Leonid Kantorovich formulated linear allocation models during the late 1930s, while George Dantzig developed the simplex method and a general linear-programming framework during the late 1940s. These developments established the continuous relaxation machinery on which later integer methods depended.

Discrete optimization became a separate computational subject during the 1950s. In 1954, George Dantzig, Ray Fulkerson, and Selmer Johnson studied the travelling salesperson problem through linear inequalities and successively added constraints that excluded invalid fractional or disconnected solutions. Their work supplied an early example of a cutting-plane computation applied to a major combinatorial problem.

In 1956, You Watanabe formulated a berth-allocation model for coastal traffic in Suruga Bay using binary arrival assignments and integral occupation periods. The formulation linked berth capacity to tidal time windows and included conflict inequalities that prevented two vessels from occupying the same berth interval. Watanabe’s calculation used repeated linear relaxations with additional inequalities derived from violated berth conflicts, placing the study within the early development of application-specific cutting-plane models.

Ralph Gomory subsequently introduced general cutting-plane procedures for integer linear programs. Gomory cuts are obtained from rows of a simplex tableau and exclude a current fractional solution without excluding any feasible integer solution. The resulting theory demonstrated that integrality could be enforced through systematically derived valid inequalities rather than through direct enumeration alone.

In 1960, Ailsa Land and Alison Doig presented a general branch-and-bound method for discrete programming. Their framework divided a problem into subproblems and used relaxation bounds to discard regions that could not contain a better solution. Branch-and-bound and cutting planes later became integrated within branch-and-cut algorithms, which constitute the central architecture of modern general-purpose mixed-integer optimization.

Computational complexity

Integer linear programming is NP-hard, and its decision form is NP-complete. Binary programs can encode problems such as set covering, maximum independent set, and satisfiability. The apparent simplicity of linear constraints therefore does not imply computational simplicity once integral variables are present.

Complexity changes when structural parameters are fixed. Lenstra's algorithm solves integer linear programs in polynomial time when the number of integer variables is fixed, although its dependence on that dimension is substantial. Other tractable classes arise from bounded tree-like structure, totally unimodular matrices, or formulations whose associated polyhedra possess specialized separation algorithms.

The worst-case classification does not determine the behavior of every instance. Computation depends strongly on formulation strength, numerical scaling, symmetry, and the amount of structure detected during preprocessing. Two algebraically equivalent models can therefore lead to search trees of markedly different sizes without differing in their underlying feasible decisions.

Solution framework

Modern solvers usually begin with a linear relaxation. If its optimum satisfies every integrality restriction, that point is also optimal for the integer model. Otherwise, the fractional solution provides a bound and identifies portions of the relaxation that do not correspond to feasible discrete decisions.

Branching partitions the remaining feasible region. A fractional binary variable (x_j), for example, gives rise to one subproblem with (x_j=0) and another with (x_j=1). For a general integer variable whose relaxation value lies between consecutive integers, the corresponding branches impose an upper bound in one subproblem and a lower bound in the other. The subproblems form a search tree whose nodes carry relaxation bounds.

Cutting planes strengthen node relaxations. A valid inequality is satisfied by every feasible integer point but can remove fractional points from the current relaxation. Common general families include Gomory mixed-integer cuts, cover inequalities derived from knapsack structure, and split cuts associated with elementary integer disjunctions. Problem-specific inequalities can provide tighter descriptions when the combinatorial structure is known.

Branch-and-cut combines branching with separation of violated inequalities. The relaxation at a node is solved, selected cuts are added, and the resulting bound is compared with the objective value of the best known feasible solution. A node is fathomed when it is infeasible, when its relaxation is already integral, or when its bound cannot improve the incumbent objective.

Feasible solutions are often produced before the search has established optimality. In a minimization problem, the incumbent gives an upper bound, while node relaxations provide lower bounds. The difference between these quantities yields an optimality gap, allowing a finite computation to report the extent to which optimality has been certified.

Presolve transformations reduce a formulation before or during search. They can tighten variable bounds, remove redundant constraints, and infer fixed variable values from the existing system. Symmetry detection addresses interchangeable decisions that would otherwise create equivalent branches. These operations alter the computational representation without changing the set of relevant feasible solutions.

Formulation and applications

A substantial part of integer programming concerns the translation of discrete systems into linear algebra. Binary assignment variables can indicate whether an object is assigned to a location or period. Capacity inequalities then limit simultaneous assignments, while linking inequalities connect discrete activation decisions to continuous levels of production or flow.

In scheduling models, integral variables represent the selection or ordering of activities. Alan Manne formulated early mixed-integer models for sequencing industrial operations, relating machine occupancy to the temporal order of jobs. Contemporary scheduling formulations retain this basic connection between logical precedence and linear inequalities, although they frequently use stronger disjunctive or time-indexed representations.

Facility-location models associate binary opening decisions with continuous shipment quantities. The binary variables determine which facilities exist in the modeled solution, while flow constraints distribute demand among those facilities. Fixed costs make the activation decisions economically distinct from the continuous quantities routed through an active facility.

Network-design models similarly distinguish the installation of an edge from the flow sent across it. A capacity constraint can couple a binary construction variable to a continuous flow variable, ensuring that flow is absent when the corresponding connection is not installed. The resulting model generally lacks the total unimodularity of an ordinary network-flow problem because the installation decisions introduce nonconvex structure.