What Is Mixed Integer Linear Programming?

Mixed integer linear programming (MILP) is a class of mathematical optimization in which some or all of the decision variables are required to take integer values, while the objective function and all constraints remain linear. When all variables must be integers, the problem is called integer programming; when only a subset must be integers and the rest may be continuous, it is the mixed integer case. The integer restriction makes MILP fundamentally harder than linear programming (LP), because the feasible region is no longer a convex polytope, and the simplex method or interior-point methods used for LP cannot directly produce integer solutions. Despite this difficulty, MILP has become one of the most broadly applied optimization frameworks in engineering, logistics, finance, and scheduling.

MILP draws its theoretical foundations from linear algebra, combinatorics, and polyhedral geometry. The discipline matured in the 1950s and 1960s alongside the development of the simplex method by George Dantzig and early integer programming algorithms by Ralph Gomory, whose cutting-plane contributions in 1958 established a central technique still used in modern solvers.

Problem Formulation

A MILP problem consists of an objective function expressed as a linear combination of decision variables, a set of linear equality and inequality constraints, variable bounds, and integrality requirements. A canonical formulation minimizes or maximizes a vector of coefficients dotted with a variable vector, subject to a constraint matrix multiplied by variables being bounded by a right-hand-side vector, with some variables restricted to integers or binary values.

Binary variables, which must equal zero or one, are particularly useful for modeling yes/no decisions: whether to open a facility, assign a worker to a shift, or include an item in a selection. These logical decisions arise naturally in network design, vehicle routing, and project scheduling, which explains why MILP is the standard formulation language for such problems. The MathWorks MILP algorithm documentation provides an accessible overview of standard formulation patterns and the solver pipeline used to resolve them.

Branch-and-Bound and Cutting Planes

The standard approach for solving MILP instances combines branch-and-bound and cutting-plane methods, a combination known as branch-and-cut. Branch-and-bound works by solving the LP relaxation of the MILP, which drops the integrality requirements and produces a lower bound on the optimal integer objective. If the LP solution has fractional values where integers are required, the algorithm branches by creating two subproblems that add constraints ruling out the fractional solution, and recursively solves each. The tree of subproblems grows until an integer-feasible solution is found or a subproblem is shown to be infeasible.

Cutting planes tighten the LP relaxation without eliminating any integer-feasible solutions, reducing the gap between the LP bound and the true integer optimum before branching begins. The arXiv survey on machine learning augmented branch and bound describes how modern MILP solvers have achieved enormous algorithmic progress by combining classical cutting-plane generation with learned heuristics for node selection, variable branching, and cut selection. Commercial solvers such as Gurobi, CPLEX, and SCIP implement these methods at scale.

Computational Complexity and Applications

MILP is NP-hard in general, meaning that no polynomial-time algorithm is known for solving arbitrary instances. In practice, however, modern solvers routinely solve instances with millions of variables and constraints, because real-world instances have structure that the solvers exploit through preprocessing, problem decomposition, and LP-quality bounds. The recent ScienceDirect survey on fifty years of integer linear programming documents the practical advances that have made large-scale MILP tractable.

Applications

Mixed integer linear programming is applied across a broad range of optimization domains, including:

• Airline crew scheduling and aircraft routing
• Supply chain network design and warehouse location selection
• Power grid unit commitment and economic dispatch
• Telecommunications network capacity planning
• Capital budgeting and portfolio construction in finance
• Production planning and job-shop scheduling in manufacturing