Mixed Integer Linear ProgrammingEdit
Mixed Integer Linear Programming (MILP) sits at the crossroads of linear optimization and combinatorial decision problems. It generalizes linear programming by allowing some decision variables to take integer values, most commonly binary choices (0 or 1) or small finite ranges. This makes MILP capable of representing a wide array of real-world decisions—where you must choose or activate options, not just rate quantities. The standard MILP framework maintains a linear objective and linear constraints, but imposes integrality on a subset of variables, which turns a convex optimization problem into a typically non-convex, combinatorial one. For optimization practitioners, MILP provides a practical, expressive modeling paradigm for discrete decisions alongside continuous decisions within a single formulation.
MILP problems can be written in the form minimize c^T x subject to A x ≤ b, with x_i ∈ Z for i ∈ I (the set of indices that must be integers) and x_j ∈ R for j ∉ I. The integrality constraints are what lift a linear programming problem into the realm of discrete optimization. The feasible set of a MILP is the intersection of a polyhedron with the integer lattice, which generally creates a non-convex search space. By contrast, the LP relaxation—where all variables are allowed to be continuous—produces a convex problem that can be solved efficiently. The gap between the LP relaxation and the best integral solution is a central driver of solver design and performance.
MILP has a long track record in both theory and practice. It is used to model facilities and networks, to schedule production and maintenance, to route vehicles, and to make on/off or yes/no decisions that accompany continuous planning. Classic examples include the facility location problem, the knapsack problem in its integer form, and various forms of job shop scheduling and [ [vehicle routing problem] ]. The breadth of applications is matched by a suite of solver technologies that have become industrial-standard tools, enabling practitioners to tackle large, complex instances with confidence.
Foundations
Problem statement and encodings
MILP blends discrete and continuous decisions. A typical formulation has decision variables x ∈ R^n, with a subset I constrained to integers. The objective is linear, usually written as min c^T x, while the constraints are linear: A x ≤ b (or Ax = b, with inequalities and equalities). Many problems encode logical or on/off decisions via integer variables: for example, a plant may be either open or closed (binary x_i ∈ {0,1}), a constraint may activate only if a feature is chosen, or a route may be selected or not selected in a logistics plan. Modern modeling tools such as AMPL, GAMS, or Pyomo let modelers express these relationships succinctly, while solvers such as CPLEX, Gurobi, or SCIP perform the heavy lifting to find optimal or near-optimal solutions.
LP relaxation and polyhedral view
Solving the LP relaxation provides a bound on the best possible objective value, since removing integrality can only improve or maintain feasibility. This bound is crucial for branch-and-bound algorithms and for assessing how far a candidate integer solution is from optimality. The geometry of MILP is underpinned by the convex hull of feasible integer points, which is generally a complicated polyhedron nested inside the original relaxation. Techniques that tighten this polyhedron—such as cutting planes—aim to trim infeasible fractional solutions without excluding any feasible integer solutions.
Variable types and modeling patterns
Binary variables (0-1) model on/off decisions, synchronization constraints, and selection among alternatives. General integer variables can encode quantities that must be whole units. Some problems use a mix of continuous variables (e.g., flow quantities) alongside integers to reflect real-valued resources and discrete decisions. Standard modeling patterns include big-M formulations to link binary decisions to linear constraints and network-flow structures that capture transportation and supply chain decisions.
Complexity and tractability
MILP is NP-hard in general, reflecting the combinatorial nature of choosing among many possible configurations while satisfying linear constraints. Lenstra’s results show that integer programming is polynomial-time solvable in fixed dimensions, but practical problems typically involve many variables and constraints. This is why solver technology emphasizes efficient bounding, problem decomposition, and effective heuristics to find good feasible solutions quickly, with certificates of optimality available when possible.
Solution methods
Branch-and-Bound
The backbone of many MILP solvers, branch-and-bound systematically explores a tree of subproblems. Each node solves an LP relaxation to obtain a bound on the best possible objective within that node’s region. If the bound is worse than the current best integer solution, the node is pruned. Otherwise, the node is split on a branching variable, creating two subproblems. Through careful selection of branching rules and strong LP relaxations, branch-and-bound can efficiently prune large portions of the search space.
Branch-and-Cut and cutting planes
Branch-and-cut augments branch-and-bound with cutting planes—linear inequalities that are valid for all feasible integer solutions but violated by the current LP relaxation. Gomory cuts, lifted inequalities, and problem-specific cuts can dramatically tighten the relaxation, reducing the number of branches needed. When combined with problem structure (e.g., network flow, scheduling), cutting planes can yield substantial performance gains.
Cutting planes and problem structure
Gomory cuts are a classical family of cuts derived directly from the current LP solution. More modern approaches include problem-specific cuts derived from network flow or facility-location structures, which exploit the combinatorial characteristics to prune infeasible regions early. These techniques are essential for solving large, real-world MILPs that would be intractable with a naïve branch-and-bound approach.
Big-M formulations and logical modeling
Big-M constraints encode conditional relationships by introducing large positive constants M. They enable modeling of implications, equivalences, and on/off constraints within a linear framework. While convenient, poorly chosen M values can lead to weak formulations and slow convergence, so practitioners seek tight formulations and problem-specific reformulations.
Heuristics, matheuristics, and hybrid approaches
When exact methods are computationally expensive, practitioners rely on heuristics and metaheuristics that deliver high-quality feasible solutions in reasonable time. Feasibility pumps, local search, and relax-and-fix strategies are common, often used in combination with exact methods to warm-start the search or to provide good incumbent solutions for pruning. The balance between solution quality and computation time is a central design consideration in industrial practice.
Applications
MILP is employed across domains where discrete decisions interact with linear cost or constraints. Examples include: - Facility location and network design, where plant or facility openings are binary decisions and flows are continuous. - Scheduling in manufacturing, transportation, and services, where timing and resource allocation are optimized under constraints. - Logistics and routing, including vehicle routing problems and related optimization of deliveries and inventories. - Energy systems optimization, such as unit commitment in power grids, where generators are turned on or off and dispatched in amounts that satisfy demand. - Financial planning and portfolio optimization, where discrete investment choices coexist with linear risk and return considerations.
These applications typically rely on high-quality formulations and leverage both exact optimization engines and industry-specific modeling patterns. The interplay between data quality, model fidelity, and solver capability determines practical solvability for large-scale problems.
Theory and practice
MILP is a mature field that blends mathematical theory with engineering practice. Key theoretical ideas include duality (and its limitations given integrality), polyhedral studies of feasible regions, and the role of convex relaxations in providing bounds. On the practical side, solver developers continuously improve heuristics, parallel processing, and memory management to handle increasingly large instances. The importance of formulation quality—how a problem is modeled—cannot be overstated: better encodings often translate into substantial speedups, even when the underlying problem structure is unchanged.
In parallel with traditional MILP, related areas such as Integer programming and Mixed integer programming research continue to explore tighter formulations, specialized cuts, and new decomposition techniques. The evolving landscape also includes integrations with data-driven methods and stochastic or robust extensions that accommodate uncertainty in model parameters.