Mixed-Integer Programming — Exact optimization over continuous and integer decisions
- Introduced by
- Ralph Gomory (branch-and-bound cuts, 1958); Land & Doig (branch-and-bound, 1960)
- Year
- 1958–1960
- Type
- Mathematical optimization
- Family
- Simulation / optimization
What does it do?
Mixed-Integer Programming (MIP) is a mathematical optimization framework in which some decision variables must take integer values while others may be continuous.
It generalizes linear programming and is widely used in operations research, logistics, scheduling, resource allocation, and engineering design, where indivisibility constraints — such as yes/no decisions or whole-unit quantities — arise naturally.
The intuition behind the method
Many real optimization problems involve decisions that cannot be split — you either open a facility or you do not, you assign exactly one worker to a shift, you order whole units. Continuous linear programming ignores these realities and can produce non-implementable fractional answers. MIP enforces integrality directly in the model. The solver explores the space of feasible integer solutions systematically via branch-and-bound: it solves relaxed continuous subproblems to bound the best possible solution in each region, discards regions that cannot improve on the best integer solution found so far, and adds cutting planes to tighten the search. The result is a provably optimal or near-optimal plan.
History
The foundations of integer programming were laid by Ralph Gomory, who introduced the cutting-plane method in 1958, and by Land and Doig, who formalized branch-and-bound in 1960. Subsequent decades saw the development of LP relaxation theory, polyhedral combinatorics (Edmonds, Padberg, Grötschel), and by the 1990s commercial solvers made large-scale MIP practical. The field is comprehensively treated in Nemhauser and Wolsey (1988) and Wolsey (1998).
When to use it
Use MIP when your problem has a linear or linearizable objective and constraints and includes decisions that must be integer-valued (facility location, crew scheduling, capital budgeting, network design, cutting-stock problems). It is the method of choice when you need a provably optimal or bounded-gap solution and problem size is tractable (thousands of variables with modern solvers). Do NOT use MIP when the objective or constraints are highly nonlinear (use nonlinear or mixed-integer nonlinear programming instead), when the problem is so large that exact methods are prohibitive (consider heuristics or metaheuristics), or when continuous approximations are accurate enough (use LP for speed).
Limitations and considerations
- Worst-case complexity is NP-hard; solve time can grow exponentially with the number of integer variables.
- Requires a precise mathematical formulation; poorly formulated models can be intractable even when the underlying problem is manageable.
- Non-convex or nonlinear elements require additional linearization or specialized solvers, increasing model complexity.
- Solver licensing costs can be significant for commercial tools, though high-quality open-source alternatives exist.
- Results are only as good as the model: incorrect constraint specification leads to meaningless optima.
Source conditions do not replace independent scientific review or validation by an analysis engine.
Strengths
- Produces provably optimal solutions with a quantifiable optimality gap, enabling rigorous decision justification.
- Handles binary and general integer variables natively, capturing real-world indivisibility and logical constraints.
- Modern solvers (Gurobi, CPLEX, SCIP) exploit advanced branch-and-bound, cutting planes, and presolve to handle large instances efficiently.
- Transparent model formulation makes assumptions explicit and auditable by domain experts.
- Supports sensitivity analysis and parametric studies to understand how solutions change with input data.
- Widely supported by modeling languages (AMPL, GAMS, Pyomo, JuMP) enabling rapid prototyping.
Applications
- Supply chain and logistics: vehicle routing, facility location, and inventory optimization with integer shipment quantities.
- Workforce scheduling: nurse rostering, crew assignment, and shift planning with binary assignment variables.
- Capital budgeting: selecting a portfolio of indivisible investment projects subject to budget constraints.
- Telecommunications and network design: capacity expansion and routing with binary link-activation decisions.
- Energy systems: unit commitment in power grids deciding which generators to switch on or off each hour.
- Manufacturing: production lot-sizing, machine scheduling, and cutting-stock problems with integer batch sizes.
How it works
How it works
Define the optimization model: an objective function (linear combination of decision variables to minimize or maximize), linear inequality and equality constraints, and integrality requirements. Continuous variables handle quantities that can be fractional; binary (0/1) or general integer variables handle discrete decisions.
Formula
\min_{x,y}\; c^\top x + d^\top y \quad \text{s.t.}\; Ax + By \leq b,\; x \geq 0,\; y \in \mathbb{Z}^pSolve the LP relaxation by temporarily dropping the integrality constraints. This gives a lower bound (for minimization) on the optimal MIP objective and a candidate solution that may be fractional.
Formula
\text{LP relaxation: replace } y \in \mathbb{Z}^p \text{ with } y \geq 0Select a fractional integer variable from the LP relaxation solution. Create two child subproblems by adding a floor constraint in one and a ceiling constraint in the other, partitioning the feasible space without losing any integer-feasible point.
Formula
\text{Select fractional } y_j^*; \text{ create subproblems: } y_j \leq \lfloor y_j^* \rfloor \text{ and } y_j \geq \lceil y_j^* \rceilSolve each subproblem's LP relaxation. If the bound is worse than the best integer solution found so far (the incumbent), prune that branch. If the LP solution happens to be integer-feasible, update the incumbent if it improves the objective.
Formula
\text{Prune node if LP bound} \geq \text{incumbent; update incumbent when integer-feasible solution found}Optionally add cutting planes — valid inequalities that cut off the fractional LP solution without removing any integer-feasible point. Gomory cuts are the classic approach; problem-specific cuts (e.g., clique cuts, flow cuts) can dramatically reduce tree size.
Formula
\text{Add Gomory or problem-specific cutting planes to tighten LP relaxation before branching}Stop when the branch-and-bound tree is fully explored or when the gap between the best integer solution and the global lower bound falls within a user-specified tolerance (e.g., 0.01%). Return the incumbent solution with its optimality certificate.
Formula
\text{Stop when all nodes pruned; return incumbent } x^*, y^* \text{ with optimality gap} \leq \epsilonCommon pitfalls
- Choosing too tight an optimality gap tolerance can make the solver run indefinitely; always set a practical gap (e.g., 1%) for large instances.
- Symmetry in the model (e.g., interchangeable facilities) creates redundant branches and blows up the search tree — use symmetry-breaking constraints.
- Weak LP relaxations (large integrality gap) lead to very large branch-and-bound trees; invest time in adding valid inequalities or tightening the formulation.
- Treating all variables as integer when only some need to be is unnecessarily costly; use binary variables only where logical constraints demand them.
- Ignoring warm-starting with a good initial feasible solution wastes solver time on finding the first incumbent.
Frequently asked questions
How is MIP different from linear programming (LP)?
LP requires all decision variables to be continuous (real-valued), which can yield fractional solutions that are physically infeasible (e.g., 2.7 trucks). MIP adds integrality constraints on some or all variables, enforcing whole-number or binary solutions at the cost of greater computational complexity.
When should I use a heuristic instead of MIP?
When the problem has millions of variables, highly nonlinear structure, or requires a near-real-time solution, exact MIP may be too slow. Metaheuristics (genetic algorithms, simulated annealing) can produce good solutions quickly, but without optimality guarantees. MIP is preferred when solution quality certification matters.
What is the optimality gap and how small should it be?
The gap is (incumbent objective - LP bound) / LP bound, expressed as a percentage. It certifies how far the best known integer solution can be from the true optimum. For most practical applications a 0.1–1% gap is sufficient; tighter gaps require exponentially more solver time.
Can MIP handle nonlinear objectives or constraints?
Standard MIP assumes linearity. Nonlinear relationships must be linearized (e.g., piecewise-linear approximation, binary expansion of products) or handled by mixed-integer nonlinear programming (MINLP) solvers, which are significantly harder to solve.
Which solvers are recommended for MIP?
Commercial: Gurobi and CPLEX are the industry benchmarks. Open-source: SCIP, CBC (via COIN-OR), and HiGHS are competitive for moderate-sized problems. All support standard modeling interfaces such as AMPL, Pyomo, and JuMP.
Related methods
Sources
Nemhauser, G. L., Wolsey, L. A. (1988). Integer and Combinatorial Optimization. Wiley-Interscience, New York.
ISBN: 9780471359432Copied.Wolsey, L. A. (1998). Integer Programming. Wiley-Interscience, New York.
ISBN: 9780471283669Copied.