Mixed-Integer Linear Programming (MILP)

Mixed-integer linear programming (MILP) is the problem class min c^T x + d^T y s.t. Ax + By ≤ b, x ≥ 0, y ∈ Z^p_+ in canonical form, where x ∈ R^n are continuous and y ∈ Z^p are integer decision variables. The integrality requirement is most often binary y ∈ {0,1}^p, modeling logical decisions (invest/not, open/close machine, use/not use route, item-supplier-period assignment). Fixed costs, discrete lot sizes, disjunctions, and big-M formulations all force integer variables. Complexity: MILP is NP-hard (Cook 1971 by SAT reduction; many of Karp's 1972 21 NP-complete problems are expressible as MILPs); the LP relaxation (dropping integrality, replacing with y ≥ 0) is polynomial and supplies a lower bound for minimization. The canonical solution algorithm is branch-and-bound, due to Land and Doig (1960) — solve the LP relaxation, branch on a fractional y_i, prune subtrees whose bound is worse than the incumbent. Gomory (1958) introduced fractional cuts, and Padberg and Rinaldi (1991) matured the branch-and-cut framework; modern solvers combine cutting planes (Gomory, lift-and-project, MIR, cover), node presolve, primal heuristics (feasibility pump, RINS), conflict analysis, and parallel branch-and-bound. Practical MILP models cover facility location (Fixed Charge Facility Location), vehicle routing, production scheduling, assignment, packing, network design, portfolio selection (cardinality constraints), and energy unit commitment.