integer programming

integer programming is a branch of mathematical optimization where some or all of the variables are required to be integers. It is a fundamental tool in operations research and management science for modeling discrete decisions, such as whether to build a facility, assign a crew, or select a route. The field has deep connections to combinatorial optimization and computational complexity theory, with foundational work advanced by researchers like Ralph E. Gomory and George Dantzig.

Definition and basic concepts

At its core, it deals with optimization problems where the feasible set is defined by linear or nonlinear constraints, and the decision variables must take on integer values. A fundamental concept is the distinction between a pure problem, where all variables are integers, and a mixed problem, which includes both continuous and integer variables. The set of feasible integer points often forms a polytope, and the challenge is to find an optimal point at a vertex of this discrete structure. Key ideas include the convex hull of integer solutions and the use of linear programming relaxations to provide bounds. The study of these structures is central to the work of institutions like the Massachusetts Institute of Technology and the IBM Thomas J. Watson Research Center.

Mathematical formulation

The canonical form for a mixed problem can be expressed as maximizing or minimizing a linear objective function subject to linear constraints, with integrality restrictions on a subset of variables. This is often written using matrix notation involving parameters defined by the American Mathematical Society. The formulation inherently creates a non-convex feasible region, making the problem far more complex than its continuous counterpart. Important special cases include the 0-1 problem, where variables are binary, modeling yes/no decisions. The theoretical underpinnings relate to areas like Diophantine equations and lattice theory, with contributions from mathematicians such as Harold W. Kuhn and Albert W. Tucker.

Solution methods

Solution techniques are broadly divided into exact and heuristic methods. The most successful exact approach is branch and bound, which enumerates candidate solutions using a tree search, pioneered by workers at the RAND Corporation. Cutting-plane methods, developed by Ralph E. Gomory, iteratively add linear constraints to tighten the linear programming relaxation. Modern solvers like CPLEX and Gurobi Optimizer combine these with sophisticated preprocessing and heuristic procedures. For particularly difficult problems, metaheuristics such as simulated annealing or genetic algorithms, inspired by work at the Santa Fe Institute, are employed to find good feasible solutions.

Complexity and computational aspects

The general problem is NP-hard, a classification established within the framework of computational complexity theory by Stephen Cook and Richard Karp. This implies that, assuming P ≠ NP, no efficient algorithm exists for all instances. However, many problems have special structures that allow for polynomial-time solutions, such as those with totally unimodular matrices or those that can be formulated as network flow problems. The practical solvability of large instances has been dramatically improved by advances in hardware and algorithms, a pursuit central to conferences like the International Symposium on Mathematical Programming.

Applications

Its applications are vast and critical to modern industry and logistics. In transportation, it is used for crew scheduling by airlines like Delta Air Lines and for vehicle routing by companies such as United Parcel Service. In manufacturing, it aids in production planning and facility location for corporations like General Motors. The telecommunications industry uses it for network design, a key concern for AT&T. Furthermore, it is essential in finance for portfolio optimization and in energy for unit commitment problems managed by entities like the Tennessee Valley Authority.

Variations and extensions

Many specialized variants address specific problem structures. Integer linear programming is the most common, but nonlinear integer programming and quadratic integer programming also exist. Stochastic programming incorporates uncertainty, a field advanced by researchers at Stanford University. Multi-objective optimization considers several conflicting goals simultaneously. Other important extensions include robust optimization, developed in response to work by Aharon Ben-Tal, and problems with additional logical constraints modeled using special ordered sets, concepts utilized in systems like the General Algebraic Modeling System.

Category:Mathematical optimization Category:Operations research Category:Computational complexity theory