Combinatorial Optimization — Math Reference

1. At a glance

Combinatorial optimization is the study of optimization problems whose decision variables range over discrete sets — permutations, subsets, integer vectors, graphs, assignments. The objective and constraints are often linear (or polynomial) in those discrete variables, but the discreteness changes everything: feasible regions are non-convex unions of points, gradients do not exist, and the search space typically grows exponentially with the input size.

Most canonical combinatorial-optimization problems (TSP, knapsack, scheduling, set cover, graph coloring, vertex cover) are NP-hard, which means that under the widely-believed conjecture P ≠ NP, no polynomial-time algorithm exists that guarantees an optimal solution on every instance. Consequently the field has split into five complementary toolkits:

1. Exact methods — ILP, branch-and-bound, branch-and-cut, dynamic programming, constraint programming, SAT/SMT. Worst-case exponential, but practical for surprisingly large instances thanks to bounding + propagation.
2. Approximation algorithms — polynomial-time algorithms with a provable performance ratio (e.g. Christofides 1976 gives 1.5-approx for metric TSP).
3. Heuristics — fast methods with no guarantee but excellent empirical quality (greedy, local search, 2-opt).
4. Metaheuristics — high-level search frameworks that escape local optima (simulated annealing, tabu, GA, ACO, LNS, CMA-ES).
5. ML-augmented — neural networks, RL, GNN, and 2024+ LLM-assisted search (FunSearch, AlphaProof).

This note is a companion to [[Math/convex-optimization]] (continuous, convex feasible regions, gradient methods) and [[Math/graph-theory]] (structural properties of the underlying graphs that most combinatorial problems are stated on).

2. Complexity classes

The complexity-theoretic backbone of combinatorial optimization is the P-vs-NP hierarchy:

• P — decision problems solvable in polynomial time on a deterministic Turing machine. Examples: shortest-path (Dijkstra O((V+E) log V)), max-flow (Orlin 2013 O(VE)), bipartite matching (Hopcroft-Karp 1973 O(E√V)), linear programming (Khachiyan 1979 ellipsoid; Karmarkar 1984 interior-point; in practice simplex).
• NP — decision problems whose YES-certificates verify in polynomial time. P ⊆ NP; equality is the open Millennium problem.
• NP-complete — the hardest problems in NP under polynomial-time reductions. Cook 1971 (“The complexity of theorem-proving procedures”) proved SAT NP-complete; Karp 1972 (“Reducibility among combinatorial problems”) then exhibited 21 NP-complete problems including 0/1-knapsack, vertex cover, clique, Hamiltonian cycle, set cover, 3-SAT, chromatic number, max cut, exact cover, feedback arc set, partition.
• NP-hard — at least as hard as NP-complete, not necessarily in NP. Optimization versions of NP-complete problems are NP-hard. TSP optimization, scheduling makespan, MIP feasibility are NP-hard.
• PSPACE — solvable with polynomial memory. Contains NP; includes generalized games.
• P — counting variants (e.g. SAT, permanent computation). Even harder than NP for most counting problems.

Implication: for any instance whose size n is large enough that 2^n or n! is intractable, optimal solutions are intractable. Practitioners must accept approximate, heuristic, or instance-specific tractable structure.

3. Classical problems

• TSP (Traveling Salesman) — given n cities with pairwise distances, find a Hamiltonian cycle of minimum total length. Symmetric (d_ij = d_ji) and asymmetric variants. NP-hard; metric TSP (triangle inequality) is APX-hard. Benchmark library: TSPLIB (Reinelt 1991, Heidelberg) — instances from 14 to 85,900 cities, exact optima all known via Concorde.
• Vehicle Routing Problem (VRP) — generalization of TSP to multiple vehicles starting from a depot. Variants: CVRP (capacitated), VRPTW (time windows), MDVRP (multi-depot), DVRP (dynamic), PDP (pickup-and-delivery). State-of-art: HGS-CVRP (Vidal 2022 hybrid genetic search) and LKH-3 (Helsgaun 2017).
• Knapsack — pack items of value v_i and weight w_i into capacity W to maximize value. Variants: 0/1 (each item once), bounded (≤ b_i copies), unbounded, multi-dimensional, multiple-knapsack. Pseudo-polynomial DP O(nW); FPTAS exists (Ibarra + Kim 1975).
• Bin packing — pack items of size s_i ∈ (0,1] into minimum number of unit bins. NP-hard; classic heuristics: First-Fit, Best-Fit, First-Fit-Decreasing (FFD ≤ 11/9 · OPT + 6/9, Dósa 2007 tight bound), 1.5-approx by Karmarkar + Karp 1982 asymptotic FPTAS.
• Scheduling — assign jobs to machines minimizing makespan (Cmax), total flow time, weighted completion, weighted tardiness ΣwjTj, lateness Lmax. Subclasses: single-machine, parallel-machine, flow-shop, job-shop, open-shop, project scheduling (RCPSP). Most variants NP-hard except a few solvable by EDD or SPT.
• Assignment problem — bipartite weighted matching: assign n workers to n jobs minimizing total cost. Hungarian algorithm (Kuhn 1955 — based on König 1931 + Egerváry 1931 Hungarian theorems) O(n³), or Jonker-Volgenant 1987 with improved constants.
• Set cover — given universe U and subsets S_i, find minimum number of subsets covering U. Chvátal 1979 showed the natural greedy gives an Hn = O(log n) approximation; this is tight unless P = NP (Feige 1998).
• Vertex cover — minimum subset of graph vertices touching every edge. 2-approx via LP relaxation + rounding (also via maximal matching). Conjectured (UGC) to have no better polytime approximation.
• Steiner tree — given graph + subset of terminals R, find minimum-weight tree connecting all R (Steiner points are free intermediate nodes). 2-approx via MST on metric closure; best known: 1.39 (Byrka et al. 2010 LP-based).
• Graph coloring — minimum colors χ(G) so adjacent vertices differ. NP-hard; greedy + DSatur (Brélaz 1979) heuristic; chromatic number is hard to approximate within n^(1−ε) (Zuckerman 2007).
• Maximum clique / maximum independent set — dual problems on G and complement. Both NP-hard; inapproximable within n^(1−ε) unless P = NP.
• Facility location — open subset of facilities at fixed cost, then assign customers minimizing assignment + opening cost. UFL (uncapacitated): 1.488-approx (Li 2013); CFL (capacitated): harder.
• Cutting stock + 1D packing — cut raw stock of length L into demanded pieces minimizing waste. Gilmore-Gomory 1961 column generation is the textbook method.
• Quadratic assignment (QAP) — assign n facilities to n locations minimizing Σ flow_ij · dist_π(i)π(j). Generalization of both linear assignment and TSP; extremely hard — instances of size n = 30 still challenge state-of-art exact solvers (QAPLIB Burkard-Karisch-Rendl 1997).

4. Exact methods

Integer Linear Programming (ILP) is the universal solvent. Formulate problem as

min  c^T x
s.t. A x ≤ b
     x ∈ Z^n  (or x ∈ {0,1}^n for binary, or mixed integer/continuous for MILP)

Solved via:

• Branch-and-bound — root LP relaxation gives lower bound; if optimal x is integer → done; else pick fractional x_i and branch into x_i ≤ ⌊x_i⌋ and x_i ≥ ⌈x_i⌉. Prune nodes whose LP bound is worse than incumbent. Land + Doig 1960 introduced; Little-Murty-Sweeney-Karel 1963 popularized for TSP.
• Branch-and-cut — at each B&B node, add cutting planes that separate the current LP vertex from the integer hull. Cut families: Gomory cuts (Gomory 1958), Mixed-Integer Rounding (MIR) (Nemhauser-Wolsey 1990), lift-and-project (Balas-Ceria-Cornuéjols 1993), flow cover, clique cuts, odd-cycle cuts. Modern Gurobi/CPLEX/SCIP add 10+ cut families automatically.
• Branch-and-price (column generation) — for LPs with exponentially many variables (e.g. one per route in VRP), keep only a small master + price out new columns by solving subproblem. Gilmore-Gomory 1961 cutting stock; Desrosiers + Lübbecke 2005 survey.
• Benders decomposition — partition variables into complicating x and easy y. Solve master in x with optimality + feasibility cuts derived from the y-subproblem dual. Benders 1962.

Dynamic programming — exploit optimal substructure:

• Knapsack: f(i, w) = max(f(i−1, w), f(i−1, w−w_i) + v_i), O(nW), pseudo-polynomial.
• TSP Held-Karp 1962 (“A dynamic programming approach to sequencing problems”, SIAM J): f(S, j) = min over i ∈ S{j} of f(S{j}, i) + d_ij. Time O(n² · 2^n), space O(n · 2^n). Optimal for n ≤ ~25.
• Shortest path with constraints — resource-constrained shortest path; used inside column generation for VRP.
• Interval scheduling — sort by end-time, then DP. O(n log n).

Constraint Programming (CP) — declarative; variables have finite domains, constraints propagate to prune domains, search picks unassigned variable and branches. Strong on scheduling, rostering, packing. Solvers:

• Google OR-Tools CP-SAT (Laurent Perron, since 2010; world-champion 2018-2024 at MiniZinc Challenge). Hybrid CP + SAT + lazy clause generation + LP. Routinely beats MIP on job-shop, rostering, vehicle dispatching.
• IBM CP Optimizer — interval variables + cumulative scheduling primitives.
• Choco — Java; academic + research.
• Gecode — C++; embeddable CP library.
• MiniZinc — high-level modeling language compiling to multiple back-ends (CP-SAT, Gecode, Chuffed).

SAT / SMT — propositional logic + theories. Encode combinatorial problem as Boolean formula; solver finds a satisfying assignment (or proves UNSAT).

• CDCL (Conflict-Driven Clause Learning) SAT solvers: MiniSat (Eén + Sörensson 2003), Glucose (Audemard + Simon 2009), Kissat (Biere 2020+, SAT Competition winner). Million-clause instances tractable.
• SMT (Satisfiability Modulo Theories): Z3 (de Moura + Bjørner, Microsoft Research 2008), CVC5 (Barrett et al. 2022), Yices (Dutertre + de Moura SRI). Theories: linear arithmetic, bit-vectors, arrays, uninterpreted functions, strings. Used in program verification, symbolic execution, planning.

MIP solvers (the workhorses):

• Gurobi — commercial, currently fastest on most MIPLIB benchmarks. Started 2008 by Bixby-Rothberg-Gu (ex-CPLEX).
• IBM CPLEX — commercial, long history from 1988 (Bixby founder); still gold standard for many corporate users.
• FICO Xpress — commercial, strong on column generation.
• HiGHS (Huangfu + Hall, Edinburgh 2018+) — open-source MIP/LP, increasingly competitive.
• SCIP (Achterberg-Berthold-Vigerske, ZIB Berlin) — open for academia, modular framework for B&B research.
• COIN-OR CBC — open MIP from COIN-OR foundation.
• LP_solve, GLPK — older open LP/MIP solvers, slow on large instances.

5. LP relaxation + duality

Dropping integrality constraints yields a Linear Program — solvable in polynomial time (Khachiyan 1979 ellipsoid; in practice simplex or interior-point). LP optimum is a lower bound for a minimization MILP (and upper bound for max). Quality of bound depends on tightness of the LP polytope; integrality gap = (IP optimum) / (LP optimum) measures looseness.

Rounding LP solutions to integer: deterministic rounding, randomized rounding (Raghavan-Thompson 1987), iterative rounding (Jain 2001 for survivable-network design), dependent rounding (Gandhi-Khuller-Parthasarathy-Srinivasan 2006). Used for many approximation algorithms.

LP duality: primal min c^T x s.t. Ax ≥ b, x ≥ 0 ↔ dual max b^T y s.t. A^T y ≤ c, y ≥ 0. Strong duality at optimum. Dual prices (“shadow prices”) drive column generation + Benders.

6. Cutting plane method

Gomory 1958 (“Outline of an algorithm for integer solutions to linear programs”, Bull AMS) — given an LP optimum xwith fractional x_i = ⌊x_i⌋ + f, the Gomory fractional cut Σ_j {a_ij} x_j ≥ f is valid for the integer hull and cuts off x. Iterating gives a finite procedure (Gomory’s terminating algorithm), but in practice slow alone.

Modern MIP combines branching + multiple cut families: Gomory mixed-integer cuts (GMI), Mixed-Integer Rounding (MIR), flow cover cuts, clique cuts, cover cuts (for 0/1 knapsack constraints), GUB cuts, implication cuts, lift-and-project, strong Chvátal-Gomory. Cut pools managed adaptively per node.

7. Branch-and-bound details

A B&B tree node = restricted subproblem (with some variables fixed/branched). At each node:

1. Solve LP relaxation → if infeasible, prune; if integer-feasible, update incumbent; if bound ≥ incumbent, prune.
2. Add cuts (branch-and-cut variant).
3. Branch — pick a variable (or constraint).
4. Select next node — best-first (lowest bound), depth-first (memory-friendly), best-estimate.

Branching strategies:

• Most-fractional — pick x_i with fractional part closest to 0.5. Cheap, often weak.
• Pseudocost branching — track historical bound improvement per variable; pick the most impactful. Bénichou et al. 1971.
• Strong branching — for each candidate, solve a tentative LP for both children, pick the one that improves bound most. Expensive but effective at the root.
• Reliability branching (Achterberg-Koch-Martin 2005) — hybrid pseudocost + strong, used in SCIP.

Node selection:

• Best-first → smallest tree but high memory.
• Depth-first → low memory, depth-bounded incumbent.
• Hybrid best-estimate dive (modern MIP default).

Primal heuristics at nodes — feasibility pump (Fischetti et al. 2005), RINS, local branching, RENS — find feasible incumbent fast to enable pruning.

8. Approximation algorithms

α-approximation: polytime algorithm that always returns a solution within factor α of optimal.

• Vertex Cover — 2-approx via LP-rounding (set x_v = 1 if LP-fractional ≥ 0.5) or via maximal matching. No better than 2 − ε under Unique Games Conjecture (Khot + Regev 2008).
• Set Cover — greedy: repeatedly pick set covering most uncovered elements. Chvátal 1979 showed ratio Hn = 1 + 1/2 + … + 1/n ≤ ln n + 1. Tight: no (1 − ε) ln n approx unless P = NP (Feige 1998).
• Metric TSP — Christofides 1976 algorithm (also independently Serdyukov 1978 in USSR): build MST, find minimum-weight perfect matching on odd-degree vertices, combine into Eulerian multigraph, shortcut to Hamiltonian. Ratio 3/2. Stood for 45 years until Karlin-Klein-Oveis Gharan 2021 gave 1.5 − ε for general metric TSP, and Sebő + Vygen 2014 had given 1.4 for graph-metric. Asymmetric TSP: O(log n / log log n) (Asadpour et al. 2010).
• Knapsack — FPTAS (Fully Polynomial-Time Approximation Scheme), Ibarra + Kim 1975: for any ε > 0, achieves (1 − ε) · OPT in time poly(n, 1/ε).
• Steiner tree — 2-approx via MST on metric closure (Takahashi-Matsuyama 1980 + Kou-Markowsky-Berman 1981). Best known 1.39 (Byrka-Grandoni-Rothvoss-Sanità 2010 LP-based).
• Max-3SAT — random assignment gives 7/8 in expectation; Håstad 2001 (“Some optimal inapproximability results”) proved 7/8 + ε is NP-hard.
• Max-Cut — Goemans + Williamson 1995 SDP rounding gives 0.878. Inapproximable beyond this under UGC.
• Bin Packing — FFD ≤ (11/9) OPT + 6/9 (Dósa 2007 tight). Asymptotic PTAS: Karmarkar + Karp 1982; AFPTAS: Plotkin-Shmoys-Tardos 1995.
• Scheduling Cmax on identical machines — LPT (longest-processing-time first, Graham 1969) is 4/3 − 1/(3m). PTAS by Hochbaum + Shmoys 1987.

9. PCP theorem

Arora-Lund-Motwani-Sudan-Szegedy 1998 (“Proof verification and intractability of approximation problems”, Journal of ACM) — every NP statement has a probabilistically checkable proof readable with O(log n) random bits + O(1) queries. Consequence: many NP-hard problems are also hard to approximate within a constant factor — there’s a gap. Spawned an entire subfield of inapproximability proofs.

Combined with Unique Games Conjecture (Khot 2002): even sharper inapproximability for max-cut, vertex cover, sparsest cut, many constraint-satisfaction problems.

10. Heuristics + metaheuristics

When you cannot afford exact, when problem structure is poorly understood, or when the model is black-box, you use heuristics. They give no guarantee but often achieve quality within a few percent of optimum in practice.

• Greedy — at each step, take the choice locally minimizing/maximizing a score. Sometimes optimal — Kruskal 1956 + Prim 1957 for MST (matroid optimality, Edmonds 1971); Dijkstra 1959 for shortest path; Huffman 1952 coding. Sometimes provably approximate (set cover). Sometimes terrible (TSP nearest-neighbor can be Θ(log n) factor worse).
• Local search — start with a feasible solution; repeatedly move to a better neighbor. Neighborhood structure is the design choice. For TSP: 2-opt (Croes 1958) reverses subsegments — O(n²) neighbors per step; 3-opt considers 3-edge swaps; Lin-Kernighan (Lin + Kernighan 1973) does variable-depth swaps. LKH-3 (Helsgaun 2000, updated 2017) is the practical state-of-art TSP/VRP heuristic — solves TSPLIB instances of 100,000+ cities within ~0.5% of optimum in minutes.
• Simulated annealing — Kirkpatrick + Gelatt + Vecchi 1983 (“Optimization by simulated annealing”, Science). Borrow Metropolis algorithm from statistical physics: accept worse moves with probability exp(−ΔE/T), decrease T over time on a cooling schedule. Theoretical convergence to global optimum under logarithmic cooling (Hajek 1988), practically used with geometric cooling.
• Tabu search — Glover 1986 (“Future paths for integer programming and links to artificial intelligence”). Local search + short-term memory (tabu list) of recently visited moves to escape cycles; aspiration criteria override tabu when beneficial; long-term memory for diversification + intensification.
• Genetic algorithm — Holland 1975 (“Adaptation in Natural and Artificial Systems”). Population of candidate solutions; selection (fitness-proportional, tournament); crossover (recombine parents); mutation (small random perturbation). Specialized GAs: NSGA-II (Deb 2002) multi-objective, HGA (hybrid GA + local search).
• Particle swarm optimization — Kennedy + Eberhart 1995 (“Particle swarm optimization”, IEEE ICNN). Population of particles in search space, each updates velocity toward personal best + global best. More natural for continuous; combinatorial variants exist.
• Ant colony optimization (ACO) — Dorigo 1992 PhD thesis, then Dorigo + Stützle “Ant Colony Optimization” 2004. Pheromone-based stochastic construction inspired by ant foraging; MAX-MIN Ant System (Stützle + Hoos 2000) is the strong variant.
• Variable neighborhood search (VNS) — Mladenović + Hansen 1997. Systematically switch neighborhood structures when stuck.
• GRASP (Greedy Randomized Adaptive Search) — Feo + Resende 1995. Randomized greedy construction + local search, repeated.
• Large-Neighborhood Search (LNS) — Shaw 1998. Destroy a chunk of the current solution + repair (often via MIP or CP). Adaptive LNS (Ropke + Pisinger 2006) adapts destroy/repair operator probabilities; dominant in VRP and routing.
• CMA-ES (Covariance Matrix Adaptation Evolution Strategy) — Hansen + Ostermeier 2001, refined 2003 (“Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES)”). State-of-art black-box continuous optimizer; adapts mutation covariance matrix from successful steps. Combinatorial variants exist via discretization.
• Iterated local search (ILS) — Lourenço-Martin-Stützle 2003. Repeat: local search → perturb → local search. Conceptually simple, surprisingly strong.

11. ML-augmented combinatorial optimization

• Graph Neural Networks for CO — Kool-van Hoof-Welling 2019 (“Attention, Learn to Solve Routing Problems!”, ICLR). Transformer/attention model + REINFORCE learns TSP/VRP/OP/PCTSP heuristic policies; competitive with classic heuristics on small instances, scales poorly to LKH-3 territory.
• Pointer networks — Vinyals-Fortunato-Jaitly 2015 — seq2seq with attention pointing to input positions, for TSP/convex-hull.
• Reinforcement learning — Bello-Pham-Le-Norouzi-Bengio 2017 (“Neural Combinatorial Optimization with Reinforcement Learning”); Khalil-Dai-Zhang-Dilkina-Song 2017 (“Learning Combinatorial Optimization Algorithms over Graphs”, NeurIPS) — Structure2Vec + DQN learns greedy heuristics for vertex cover, max-cut, TSP.
• Survey — Mazyavkina-Sviridov-Ivanov-Burnaev 2021 “Reinforcement Learning for Combinatorial Optimization: A Survey”, Computers & OR.
• Neural Combinatorial Optimization + Learning to Optimize — meta-learning of solver heuristics, branch decisions, cut selection. Gasse-Chételat-Ferroni-Charlin-Lodi 2019 “Exact Combinatorial Optimization with Graph Convolutional Neural Networks” learns variable-selection in MIP B&B.
• Decision-focused learning — Wilder-Dilkina-Tambe 2019 “Melding the data-decisions pipeline” — train ML predictor with downstream optimization loss directly, not prediction loss.
• 2024+ frontier:
  • FunSearch (DeepMind, Romera-Paredes et al. 2023, Nature 2024) — LLM proposes Python heuristic programs, evaluator scores, evolutionary search across generated code. Discovered new constructions for cap-set + bin-packing.
  • AlphaProof (DeepMind 2024) — RL + Lean theorem proving; silver-medal IMO 2024 (4/6 problems).
  • OpenAI o1 / o3 — chain-of-thought RL’d LLMs; competitive on olympiad math + competitive programming.
  • AlphaCode 2 — competitive-programming LLM (Google DeepMind 2023).

12. Specific algorithms for famous problems

• TSP:
  • Exact: Held-Karp DP O(n² · 2^n), good for n ≤ 25. Concorde (Applegate-Bixby-Chvátal-Cook 2003, “The Traveling Salesman Problem: A Computational Study” 2006) — branch-and-cut with custom TSP cuts (subtour elimination, comb, clique-tree); solved pla85900 (85,900 cities) to provable optimality 2006, and the LIN318/RL11849 series along the way.
  • Heuristic state-of-art: LKH-3 (Helsgaun 2017) — variable-depth Lin-Kernighan with sophisticated edge candidate sets (α-nearness from minimum 1-tree); regularly solves 100K-city instances within 0.5%.
  • ML approaches: still trail LKH-3 in quality at scale.
• VRP: HGS-CVRP (Vidal 2022) hybrid genetic with intensive local search + Split decoder; LKH-3 for capacitated + time-windows; Google OR-Tools routing for production use.
• Job-shop scheduling: OR-Tools CP-SAT routinely beats Taillard + Demirkol benchmarks; lazy clause generation + portfolio search. SCIP-Jack for job-shop with side constraints.
• Knapsack: DP for moderate W; Pisinger 1997 “A minimal algorithm for 0-1 knapsack” — combo + expanding-core algorithm, fast on hard instances; greedy by v_i/w_i ratio is optimal for fractional knapsack only.
• SAT solving: CDCL (Conflict-Driven Clause Learning) descended from DPLL (Davis-Putnam-Logemann-Loveland 1962). Modern winners: Kissat (Biere 2020-2024), CaDiCaL (Biere), Glucose, MapleSAT.
• SMT: Z3 is the workhorse (Microsoft Research, open since 2015); CVC5 for richer theories (strings, sequences, finite fields); Yices for QF-LIA + bit-vectors.
• Min-cost flow / assignment: network simplex (Orlin 1997); auction algorithms (Bertsekas 1979); Jonker-Volgenant 1987 for assignment.
• Max-flow: Dinic 1970 O(V²E); Goldberg-Tarjan push-relabel 1988; Orlin 2013 strongly polynomial O(VE).
• Matching: blossom algorithm (Edmonds 1965) for general graphs O(V²E); Micali-Vazirani 1980 O(E√V) — implemented in Boost + LEMON.

13. Software

• Google OR-Tools (Perron + Furnon, since 2010) — open-source: CP-SAT, MIP wrappers, routing, assignment, graph algorithms, knapsack. Probably the most widely used combinatorial-optimization library 2018+. Python/C++/Java/.NET bindings.
• Gurobi — commercial gold-standard MIP/QP/SOCP/QCP solver. Free academic license. Fastest on most MIPLIB.
• IBM CPLEX — commercial; older + still strong on enterprise + free for academia.
• FICO Xpress — commercial; strong on column generation + presolve.
• HiGHS — open-source LP/MIP from Edinburgh (Huangfu, Hall 2018+); the fastest free MIP for many instance classes.
• SCIP — open framework for B&B + cuts; standard for academic CP/MIP/MINLP research.
• COIN-OR CBC, GLPK, LP_solve — older open MIP/LP solvers.
• Modeling layers:
  • AMPL — commercial, classic algebraic modeling language.
  • GAMS — commercial, energy + economics tradition.
  • Mosel (FICO Xpress).
  • JuMP (Julia, Lubin-Dunning-Hijazi 2017+).
  • Pyomo (Sandia, Hart et al.) — Python.
  • PuLP — lightweight Python MIP modeling.
  • cvxpy — Python; convex modeling but supports MIQP/MISOCP via Gurobi/Mosek (see [[Math/convex-optimization]]).
• MiniZinc (Stuckey et al., Monash) — high-level CP modeling language → CP-SAT, Chuffed, Gecode back-ends. MiniZinc Challenge is the annual CP solver benchmark.
• Concorde (Applegate-Bixby-Chvátal-Cook) — TSP exact branch-and-cut solver; free for academic use.
• LKH-3 (Helsgaun) — TSP/VRP heuristic; free for academic use.
• HGS-CVRP (Vidal) — open-source CVRP/VRPTW state-of-art.
• Z3, CVC5, Yices, Kissat, Glucose, MiniSat — SAT/SMT solvers.
• LEMON, igraph, NetworkX, Boost.Graph — general graph algorithms (max-flow, matching, MST, shortest path).

14. Approximation difficulty hierarchy

• PTAS (Polynomial-Time Approximation Scheme) — for any ε > 0, polytime (1+ε)-approx; runtime polynomial in n but possibly exponential in 1/ε. Example: Euclidean TSP (Arora 1998, Mitchell 1999 — both with PTAS).
• FPTAS — runtime polynomial in both n and 1/ε. Example: 0/1 Knapsack (Ibarra-Kim 1975).
• EPTAS — runtime f(1/ε) · poly(n), separating ε-dependence.
• APX — admits a constant-factor approximation. Example: Vertex Cover, metric TSP.
• APX-hard — no PTAS unless P = NP (assuming PCP theorem). Examples: Max-3SAT, vertex cover, metric TSP, bin packing.
• Log-APX — best ratio is Θ(log n). Example: set cover.
• Poly-APX — best ratio is polynomial in n. Example: independent set.

Unique Games Conjecture (Khot 2002) — implies sharper inapproximability bounds for vertex cover (no better than 2 − ε), max-cut (no better than 0.878), and many CSPs. Major open problem; if true, Goemans-Williamson and many LP/SDP-based approximations are exactly tight.

15. Industrial applications

• Logistics:
  • VRP for last-mile delivery — UPS ORION (On-Road Integrated Optimization and Navigation, 2013 deployment) reportedly saved 100 million miles + 10 million gallons of fuel per year.
  • Amazon last-mile + DSP routing.
  • Food delivery dispatch — DoorDash, Uber Eats use real-time variants of VRP + bipartite matching.
• Manufacturing — job-shop scheduling (foundry, semiconductor fab dispatching), supply chain network design (cross-reference [[Engineering/supply-chain-management]]), capacity planning, MRP.
• Telecom — network design (Steiner tree, k-edge-connected), frequency assignment (graph coloring), call routing.
• Energy — unit commitment (MILP: which generators on/off when, billion-dollar problem solved daily by every ISO), optimal power flow (MINLP/MISOCP), gas/water network design, EV charging scheduling.
• Finance — portfolio optimization with cardinality + lot-size constraints (MIQP, see [[Math/convex-optimization]]), index tracking, basket trading, optimal execution.
• Healthcare — surgery scheduling (Belien-Demeulemeester 2007), nurse rostering (NRP benchmark), radiation-therapy planning (MILP/MIQP), kidney exchange (Saidman-Roth-Sönmez-Ünver 2006 matching).
• Sports — schedule optimization: NFL, MLB, NHL, NBA, NCAA all use ILP for schedule construction; UEFA Champions League draw is structured combinatorial problem.
• Crew scheduling — airline crew pairing + rostering — column generation on huge VRPs (American, Delta, United run multi-day MIP solves).
• Compilers — register allocation as graph coloring (Chaitin 1981); instruction scheduling as resource-constrained job-shop; basic-block layout, branch placement.
• Bioinformatics — protein folding (now mostly AlphaFold ML), DNA assembly + sequencing, RNA secondary structure, drug design (ML + combinatorial).
• Chip design — VLSI placement (quadratic + simulated annealing + force-directed); routing (Steiner trees + global router); register-transfer-level scheduling; clock-tree synthesis; now increasingly ML-augmented (Google’s chip-placement RL, Mirhoseini et al. 2021 Nature).
• OS / cloud — VM placement (bin packing), task scheduling in clusters (Kubernetes scheduler is a heuristic for a generalized assignment + packing), Google Borg, container scheduling.

16. Modeling tips

• Choose decision variables carefully — flow vs. assignment vs. position-based formulations can change LP relaxation tightness by orders of magnitude. Pour over Wolsey “Integer Programming” 2020 + Williams “Model Building in Mathematical Programming” 2013.
• LP relaxation tightness matters more than constraint count — sometimes adding 10⁵ valid inequalities to make the relaxation tight is faster than a sparse formulation with weak bound. Mileage: extended formulations (Conforti-Cornuéjols-Zambelli 2014) trade variable count for relaxation tightness.
• Add valid inequalities — facet-defining when possible; even non-facet cuts often help.
• Use indicator variables judiciously — big-M formulations work but big-M magnitude matters: too large = weak LP, numerical noise; too small = wrong answers. Indicator constraints in modern MIP (Gurobi, CPLEX) handle this internally — prefer them.
• Symmetry-breaking constraints — if interchanging item 1 and item 2 gives the same objective, add x_1 ≥ x_2 or lex ordering. Symmetry kills B&B trees; orbital + isomorphism pruning (Margot 2002, Salvagnin 2018) helps.
• Presolve does a lot — modern MIP solvers reduce model size by 30-90% before search. Don’t pre-tighten manually unless the solver misses something domain-specific.
• Warm starts — initial feasible solution (even from a heuristic) drastically improves MIP performance by enabling early pruning.
• Decomposition when natural — Benders for two-stage stochastic, Lagrangian for coupling constraints, Dantzig-Wolfe for block structure.

17. Pitfalls

• Loose LP relaxation → exponential B&B tree. If you see a 50% gap after 10 minutes, your formulation is probably the problem, not the solver. Check facet inequalities, extended formulations.
• Big-M too large → numerical issues, weak relaxation. Use indicator constraints or tightened big-M (compute the smallest M that’s valid given variable bounds).
• Ignoring CP-SAT for scheduling — for job-shop, RCPSP, and rostering, OR-Tools CP-SAT often crushes MIP because cumulative + interval propagation prunes far more than LP rounding ever could.
• Hand-coded heuristic when OR-Tools / LKH would solve — production teams often write a custom Python greedy when 50 lines of MIP would give optimal. Profile first.
• Not warm-starting iterative MIP solves — when re-solving daily/hourly (production scheduling), feed last solution as MIP-start. 10-100× speedup typical.
• Mixing units / scaling — MIP solvers degrade when coefficients span more than 10⁹ in magnitude. Rescale variables + constraints.
• Symmetry left unbroken — n! equivalent solutions ⇒ n! × work.
• Stochasticity not modeled — if inputs are uncertain, deterministic MIP gives brittle solutions. Use stochastic programming, robust optimization, or chance constraints (Birge + Louveaux 2011).
• Local-search restarts not diversified — if all restarts converge to the same basin, you’re stuck. Use ILS with strong perturbation, or LNS with destroy/repair pairs that cover different neighborhood structures.

18. Cross-references

• [[Math/convex-optimization]] — continuous optimization, LP/QP/SDP, the substrate that ILP relaxation lives on; MIQP/MISOCP bridge.
• [[Math/graph-theory]] — combinatorial problems mostly live on graphs; MST, matching, flow, coloring are graph-theoretic.
• [[Math/_index]] — Math MOC.
• [[Engineering/supply-chain-management]] — VRP, facility location, network design applications.
• [[Engineering/Tier3/machining-processes]] — job-shop + flow-shop scheduling.
• [[Robotics/Tier3/path-planning-algorithms]] — TSP variants for robot routing, lawnmower coverage, RRT-variants.
• [[Compute/_index]] — solver implementations + compute-hardware angle.

19. Citations

• Schrijver, A. “Combinatorial Optimization: Polyhedra and Efficiency” (3 volumes), Springer 2003 — encyclopedic reference.
• Cook, W., Cunningham, W., Pulleyblank, W., Schrijver, A. “Combinatorial Optimization” Wiley 1998 — graduate textbook.
• Wolsey, L. “Integer Programming” 2nd ed Wiley 2020 — the standard MIP textbook.
• Conforti, M., Cornuéjols, G., Zambelli, G. “Integer Programming” Springer 2014 — polyhedral theory + extended formulations.
• Williams, H.P. “Model Building in Mathematical Programming” 5th ed Wiley 2013 — formulation craft.
• Applegate, D., Bixby, R., Chvátal, V., Cook, W. “The Traveling Salesman Problem: A Computational Study” Princeton 2006 — Concorde + the largest exact TSP solves.
• Karp, R. 1972 “Reducibility among Combinatorial Problems” — the 21 NP-complete list.
• Cook, S. 1971 “The complexity of theorem-proving procedures”, STOC — Cook-Levin theorem.
• Christofides, N. 1976 “Worst-case analysis of a new heuristic for the travelling salesman problem”, CMU TR — 3/2-approx for metric TSP.
• Held, M., Karp, R. 1962 “A dynamic programming approach to sequencing problems”, SIAM Journal — Held-Karp DP.
• Kirkpatrick, S., Gelatt, C.D., Vecchi, M.P. 1983 “Optimization by simulated annealing”, Science — SA.
• Holland, J. 1975 “Adaptation in Natural and Artificial Systems” — GA.
• Glover, F. 1986 “Future paths for integer programming and links to artificial intelligence”, Computers & OR — tabu search.
• Dorigo, M. 1992 PhD thesis Politecnico di Milano — Ant Colony.
• Helsgaun, K. 2000 “An effective implementation of the Lin-Kernighan traveling salesman heuristic”, EJOR — LKH.
• Helsgaun, K. 2017 “An extension of the Lin-Kernighan-Helsgaun TSP solver for constrained traveling salesman and vehicle routing problems”, Roskilde — LKH-3.
• Lin, S., Kernighan, B. 1973 “An effective heuristic algorithm for the traveling-salesman problem”, Operations Research — original LK.
• Chvátal, V. 1979 “A greedy heuristic for the set-covering problem”, Math of OR — set-cover Hn bound.
• Gomory, R. 1958 “Outline of an algorithm for integer solutions to linear programs”, Bull AMS — cutting planes.
• Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M. 1998 “Proof verification and the hardness of approximation problems”, J ACM — PCP theorem.
• Håstad, J. 2001 “Some optimal inapproximability results”, J ACM.
• Khot, S. 2002 “On the power of unique 2-prover 1-round games”, STOC — UGC.
• Goemans, M., Williamson, D. 1995 “Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming”, J ACM.
• Kool, W., van Hoof, H., Welling, M. 2019 “Attention, Learn to Solve Routing Problems!”, ICLR — attention model for TSP/VRP.
• Bello, I., Pham, H., Le, Q., Norouzi, M., Bengio, S. 2017 “Neural Combinatorial Optimization with Reinforcement Learning”.
• Khalil, E., Dai, H., Zhang, Y., Dilkina, B., Song, L. 2017 “Learning Combinatorial Optimization Algorithms over Graphs”, NeurIPS.
• Mazyavkina, N., Sviridov, S., Ivanov, S., Burnaev, E. 2021 “Reinforcement Learning for Combinatorial Optimization: A Survey”, Computers & OR.
• Romera-Paredes, B. et al. (DeepMind) 2024 “Mathematical discoveries from program search with large language models”, Nature — FunSearch.
• Karlin, A., Klein, N., Oveis Gharan, S. 2021 “A (slightly) improved approximation algorithm for metric TSP”, STOC.
• Vidal, T. 2022 “Hybrid genetic search for the CVRP: open-source implementation and SWAP* neighborhood”, Computers & OR — HGS-CVRP.
• Perron, L., Furnon, V. “OR-Tools” Google, docs at developers.google.com/optimization.
• Pisinger, D. 1997 “A minimal algorithm for the 0-1 knapsack problem”, Operations Research.
• Ibarra, O., Kim, C. 1975 “Fast approximation algorithms for the knapsack and sum of subset problems”, J ACM — FPTAS.
• Kuhn, H. 1955 “The Hungarian method for the assignment problem”, Naval Research Logistics.
• Edmonds, J. 1965 “Paths, trees, and flowers”, Canadian J Math — matching blossom algorithm.
• Achterberg, T., Koch, T., Martin, A. 2005 “Branching rules revisited”, OR Letters — reliability branching.
• Land, A., Doig, A. 1960 “An automatic method for solving discrete programming problems”, Econometrica — B&B origin.
• Benders, J. 1962 “Partitioning procedures for solving mixed-variables programming problems”, Numer Math.
• Birge, J., Louveaux, F. 2011 “Introduction to Stochastic Programming” 2nd ed Springer.
• Feige, U. 1998 “A threshold of ln n for approximating set cover”, J ACM.
• De Moura, L., Bjørner, N. 2008 “Z3: An efficient SMT solver”, TACAS.
• Eén, N., Sörensson, N. 2003 “An extensible SAT-solver” — MiniSat.

End of reference.