Mixed-Integer Programming
Mixed-integer programming combines continuous and integer variables, letting a single model capture both discrete decisions and continuous quantities.
Mixing discrete and continuous
A mixed-integer program (MIP) has some variables constrained to be integer and others free to take real values. This matches most real decisions: choose which plants to open (integer) and how much each produces (continuous); decide whether a link is built (binary) and how much flow it carries (continuous). Mixed-integer linear programs (MILP) have linear objectives and constraints; mixed-integer nonlinear programs (MINLP) allow nonlinear ones.
The relaxation-and-branch structure
MIPs are solved by branch and cut. At each node the integrality of the integer variables is relaxed, yielding an LP (for MILP) whose solution gives a bound. If the relaxed integer variables come out fractional, the solver branches on one of them, splitting into subproblems, and adds cutting planes to tighten the relaxation. The continuous variables ride along in the LP and never need branching.
Cuts, heuristics, presolve
Performance comes from three additions layered on branch and bound. Cutting planes (Gomory, cover, flow, clique cuts) tighten the relaxation without cutting off integer solutions. Primal heuristics (rounding, feasibility pump, local search) find good incumbents quickly to power pruning. Presolve removes redundant constraints and tightens bounds before search begins. Together these routinely turn intractable-looking models into solvable ones.
- MILP: linear, solved robustly by mature commercial and open solvers
- MINLP: harder; convex MINLP is tractable, nonconvex needs global methods
- Warm starts: reuse a prior solution when re-solving a similar model
- Optimality gap: the reported certificate of solution quality on early stop
Where it fits
MIP is the workhorse for planning problems that blend logic with physics: production planning, energy dispatch with commitment decisions, vehicle routing, and layout. In engineering design it handles the frequent case where a design has both catalog choices (a component present or not, a discrete number of units) and continuous sizing parameters, optimized jointly rather than in separate passes.