## Definition **Integer Linear Programming (ILP)** is a Linear Programming problem where some or all variables are restricted to integer values. **Mixed Integer Linear Programming (MILP)** mixes continuous and integer variables. Vastly more expressive — and vastly harder — than pure [[Linear Programming]]. ## Standard Form $ \min \, c^\top x \quad \text{subject to} \quad A x \leq b, \quad x \in \mathbb{Z}^n_{\geq 0} $ Variants: - **Pure ILP:** all integers. - **MILP:** some integer, some continuous. - **Binary ILP (BIP):** all variables $\in \{0, 1\}$. ## Why Integers Make It Hard The feasibility region becomes a discrete set of lattice points within a polytope — not convex, not differentiable, not navigable by smooth methods. ILP is **NP-hard**; the best general algorithms are exponential in the worst case. ## What Integer Decisions Buy Integer variables model decisions that aren't representable in pure LP: - **Yes/no choices** ($x \in \{0, 1\}$): "build this facility or not". - **Discrete quantities** ($x \in \mathbb{Z}$): "ship 1 or 2 or 3 containers". - **Either/or logic** via Big-M constraints. - **Indicator constraints**: "if x > 0 then y ≤ 5". ILP unlocks combinatorial decision problems that LP cannot express. ## Algorithms ### LP Relaxation Drop the integrality constraints. Solve the resulting LP. The optimum gives a *bound*: - For minimisation: LP optimum ≤ ILP optimum (LP is "easier"). - For maximisation: LP optimum ≥ ILP optimum. If the LP solution happens to be integer, it's also the ILP solution. (Rare in general.) ### [[Branch and Bound]] Systematically branch on fractional variables in the LP relaxation. At each node, solve an LP; if the bound is worse than the current best integer solution, prune. ### [[Branch and Cut]] Branch-and-bound + cutting planes: add valid inequalities (cuts) at each node to tighten the LP relaxation before branching. ### Heuristics For very large MILPs: - **Rounding heuristics.** Round LP solution; repair infeasibilities. - **Feasibility pump.** Alternates between LP-optimal and integer-feasible solutions. - **Local search.** Improve an existing integer solution. Commercial solvers (Gurobi, CPLEX) combine all of these. ## Modern Solvers The state of the art (2026): - **Gurobi, CPLEX** — commercial leaders. - **OR-Tools CP-SAT** — Google's open-source, combines MILP with constraint propagation. - **HiGHS** — open-source MILP solver. - **SCIP** — academic / research solver. These routinely solve MILPs with millions of variables that would have been impossible 20 years ago. ## Where ILP Wins - **Scheduling.** Production planning, employee shifts. - **Logistics.** Routing, vehicle assignment, network design. - **Telecommunications.** Wavelength assignment, frequency planning. - **Finance.** Portfolio optimisation with cardinality constraints. - **Manufacturing.** Lot sizing, capacity planning. ## When Not to Use ILP - **Massive scale.** Solvers eventually choke; consider Lagrangian decomposition or specialised methods. - **Soft constraints throughout.** When constraints are flexible, pure ILP can be brittle; multi-objective or constraint-programming formulations help. - **Online problems.** ILP is best for static optimisation; for streaming decisions, heuristics often win. ## Connection to Boolean Satisfiability Pure BIP can be reduced to SAT and vice versa. Modern MILP solvers borrow techniques from SAT (conflict-driven clause learning, restart strategies). The line between MILP and SAT solving has blurred. ## Related - [[Linear Programming]] - [[Branch and Bound]] - [[Branch and Cut]] - [[Combinatorial Optimization]]