Mixed-Integer Linear Programming (MILP)
Mixed-Integer Linear Programming (MILP) is one of the most important and widely used problem classes in operations research and optimization. It extends Linear Programming (LP) by allowing some decision variables to take integer or binary values, enabling the modeling of discrete choices, logical conditions, and combinatorial structures that arise in real-world decision problems.
MILP plays a central role in applications such as supply chain design, production planning, scheduling, network design, energy systems, and finance.
What is Mixed-Integer Linear Programming?
Formally, a mixed-integer linear program is an optimization problem in which:
- The objective function is linear,
- All constraints are linear equalities or inequalities,
- Some decision variables are required to be integer-valued, while others may remain continuous.
A standard MILP can be written as:
- Minimize or maximize a linear objective function
- Subject to linear constraints
- With x_i \in \mathbb{Z} for some variables and x_j \in \mathbb{R} for others
If all variables are continuous, the problem reduces to a linear program. If all variables are integer, the problem becomes an integer linear program (ILP).
Solving Mixed-Integer Linear Programs
The feasible region of a Mixed-Integer Linear Program is no longer a convex polytope, but rather a discrete subset of the LP polytope. This loss of convexity fundamentally changes how such problems must be solved.
Unlike linear programs, MILPs cannot be solved efficiently by a single polynomial-time algorithm. Instead, modern solvers rely on enumerative and relaxation-based techniques, most notably:
- Branch-and-Bound, which systematically explores subsets of the integer search space using LP relaxations for bounds,
- Branch-and-Cut, which strengthens the LP relaxations by dynamically adding valid inequalities (cutting planes),
- Branch-and-Price, which combines Branch-and-Bound with column generation based on Dantzig–Wolfe decomposition,
- Branch-Cut-and-Price, which integrates all of the above.
LP relaxations are central to all these methods. Indeed, at each node of the search tree, a linear programming problem is solved to provide bounds and guide branching decisions.
Extensions and related problem classes
Mixed-Integer Linear Programming (MILP) sits at the crossroads of many optimization paradigms:
- It generalizes Linear Programming (LP) by introducing integrality constraints.
- It is a special case of Mixed-Integer Nonlinear Programming (MINLP) when all nonlinearities are removed.
- It often serves as a modeling foundation for combinatorial optimization problems such as routing, scheduling, and facility location.
Because of its flexibility, MILP is frequently used as a unifying modeling language even when problems are ultimately solved using heuristics, decomposition methods, or hybrid approaches.
Further reading and references
Nemhauser, G. L., & Wolsey, L. A. (1988). Integer and Combinatorial Optimization. Wiley.
A definitive theoretical reference on integer and mixed-integer optimization, covering polyhedral theory, cutting planes, and complexity. Widely regarded as a foundational text in the field.
Wolsey, L. A. (1998). Integer Programming. Wiley.
A classic textbook focusing on modeling, formulation strength, and algorithmic techniques for integer and mixed-integer linear programs.
Gomory, R. E. (1960). An Algorithm for Integer Solutions to Linear Programs. In Recent Advances in Mathematical Programming.
A landmark paper formalizing cutting planes for integer programming, which remain a core component of modern MILP solvers.