Combinatorial optimization
The theory part of a self-study course: 34 slide decks with speaker notes,
clickable glossary terms (press G in a deck), a reading mode (R) and M to come back here, plus optional interactive
figures. The labs, their tests and the reference solutions are not part of this site; commands such as
uv run co lab 07 in the decks refer to the course repository. See also the
curriculum.
Part 0 the ground floor
-
00
Models, instances, and an oracle you trust
What a combinatorial problem is, the nine you will meet all course, and the one tool that lets you believe your own code.
slides · reading mode · interactive figuresspine · needs nothing · ~1¼ h
Part I trunk A · linear programming
-
01
Polyhedra, cones, and Farkas' lemma
The shape of a feasible region, three names for its corners, and a short proof that a linear system has no solution.
slides · reading mode · interactive figuresspine · needs 00 · ~2 h
-
02
Simplex, honestly
Walking from vertex to better vertex: why it works, when it loops forever, when it takes exponentially long, and why it is still the workhorse.
slides · reading mode · interactive figuresspine · needs 01 · ~2 h
-
03
Duality — the load-bearing unit
Every LP has a shadow LP that bounds it, prices its constraints, certifies its optimum, and re-solves it cheaply after a change.
slides · reading mode · interactive figuresspine · needs 02 · ~2½ h
-
04
Polynomial-time LP: ellipsoid and interior point
Two ways through the middle of the polyhedron: one that settled a theoretical question and is never used, and one that runs in every modern solver.
slides · reading mode · interactive figuresbranch · needs 02 · ~2 h
Part II trunk A · integer programming
-
05
Formulations, relaxations, and the integrality gap
The same integer solutions, described by different polyhedra, and why the choice decides whether a solver finishes.
slides · reading mode · interactive figuresspine · needs 03 · ~2 h
-
06
Total unimodularity: when integrality is free
The structural reason assignment, transportation and flow problems need no branching, and the smallest structure that ends it.
slides · reading mode · interactive figuresbranch · needs 03 · ~1½ h
-
07
Branch and bound
Split the problem, bound each piece with an LP, and throw away every piece that cannot win. What to split on and which piece to look at next decide everything.
slides · reading mode · interactive figuresspine · needs 05 · ~2 h
-
08
Cutting planes and branch-and-cut
Inequalities that every integer solution satisfies and the LP optimum doesn't: how to derive them, how to find them, and why solvers throw most of them away.
slides · reading mode · interactive figuresspine · needs 07 · ~2 h
-
09
Separation ⇔ optimization
You can optimize over a polytope in polynomial time exactly when you can find a violated inequality in polynomial time. Exponentially many constraints are fine.
slides · reading mode · interactive figuresbranch · needs 04, 08 · ~2 h
-
10
Column generation, Dantzig–Wolfe, branch-and-price
LPs with more columns than atoms, solved by asking a pricing problem one question at a time. The duals of unit 03 become the objective of a combinatorial subproblem.
slides · reading mode · interactive figuresspine · needs 08, 16 · ~2 h
-
11
Lagrangian relaxation and subgradient methods
Price the hard constraints into the objective and solve what is left. Every price gives a bound; the best price gives exactly the bound you can predict in advance.
slides · reading mode · interactive figuresspine · needs 03, 16 · ~1¾ h
-
12
Benders decomposition
Fix the hard variables, let the easy ones' duals write an inequality about the choice, and repeat. Row generation — the mirror image of unit 10.
slides · reading mode · interactive figuresbranch · needs 10 · ~1¾ h
Part III trunk B · combinatorial algorithms
-
13
Matroids and the exact reach of greedy
Greedy is optimal for every choice of weights exactly when the feasible sets form a matroid, which answers "when does this heuristic work?" completely.
slides · reading mode · interactive figuresspine · needs 00 · ~2 h
-
14
Network flows
Max-flow min-cut, three algorithms and why each exists, costs and potentials, and the skill that matters most: recognizing a flow in disguise.
slides · reading mode · interactive figuresspine · needs 13 · ~2 h
-
15
Matching
König and Hall, Hopcroft–Karp, the Hungarian method as primal–dual with its certificate in plain sight, Edmonds' blossoms, and stable matching for contrast.
slides · reading mode · interactive figuresspine · needs 14 · ~2 h
-
16
Dynamic programming over combinatorial structure
Shortest paths in a DAG of states; knapsack and what "pseudo-polynomial" really means; Held–Karp; trees, treewidth and Courcelle; the vocabulary of parameterised complexity.
slides · reading mode · interactive figuresspine · needs 15 · ~2 h
Part IV trunk C · constraint programming and SAT
-
17
Constraint satisfaction and propagation
Variables, domains, constraints — and no relaxation. Remove what cannot be part of a solution, search over what remains, undo, repeat.
slides · reading mode · interactive figuresspine · needs 00 · ~1½ h
-
18
Global constraints and their filtering algorithms
One constraint that sees the whole structure beats many that each see a pair. Matching filters alldifferent; compulsory parts filter cumulative; the price is paid per call.
slides · reading mode · interactive figuresspine · needs 17, 15 · ~1¾ h
-
19
Search, restarts, and large neighbourhood search
Which variable next, which value first, when to give up and start again — and how destroy-and-repair turns an exact engine into a heuristic that scales.
slides · reading mode · interactive figuresspine · needs 18 · ~1¾ h
-
19b
Backjumping, and why search is complete
When a dead end has nothing to do with the last choice, go back to the choice that caused it. Why a search that skips subtrees this way still misses no solution, and why it always stops.
slides · reading mode · interactive figuresneeds 19 · ~1½ h
-
20
SAT and the CDCL engine
Unit propagation, conflict analysis, backjumping, activity, restarts — resolution with a very good heuristic, and a proof system with limits you can state precisely.
slides · reading mode · interactive figuresspine · needs 17 · ~2 h
-
21
Lazy clause generation, or what CP-SAT actually is
Propagators that explain themselves as clauses, a CDCL engine that learns from them, and a linear relaxation running alongside: the hybrid that ate the field.
slides · reading mode · interactive figuresbranch · needs 19, 20 · ~1½ h
Part V where the trunks converge
-
22
Hardness, and the shape of what is possible
Reductions as programs, the numbers that make a problem hard, and the hierarchy of how close to optimal a polynomial algorithm can promise to get.
slides · reading mode · interactive figuresspine · needs 11 (and 00, 16, 20) · ~1½ h
-
23
Combinatorial approximation algorithms
Greedy, matchings, spanning trees and sorting, each with a lower bound on the optimum it can compute, and a proof that fits on one slide.
slides · reading mode · interactive figuresspine · needs 22, 16, 15, 13 · ~1½ h
-
24
LP rounding and the primal–dual method
One lower bound for everything: the LP relaxation. Round its solution, or grow its dual and buy what the dual pays for. Either way, its integrality gap is the limit.
slides · reading mode · interactive figuresspine · needs 23, 03 · ~1½ h
-
25
Semidefinite relaxations
Give each vertex a vector instead of a number, constrain only inner products, and round with a random hyperplane: Goemans–Williamson's 0.878, the Lovász theta function, and the hierarchies above them.
slides · reading mode · interactive figuresbranch · needs 24, 04 · ~1½ h
-
26
Metaheuristics, benchmarked honestly
Local search engineered properly, the handful of metaheuristics worth knowing, and what a comparison between randomised algorithms has to hold fixed before it means anything.
slides · reading mode · interactive figuresspine · needs 24, 19 · ~1½ h
Part VI making it real
-
27
Modelling for a real solver
What presolve does and what defeats it, symmetry, big-M against indicators, starts, reading the log, and the discovery that most single-run speed-ups are noise.
slides · reading mode · interactive figuresspine · needs 26, 08 · ~1½ h
-
28
Experimental method
Summaries that don't lie, pictures that answer the right question, intervals and tests for claims about randomised and chaotic solvers, and an audit of this course's own earlier conclusions.
slides · reading mode · interactive figuresspine · needs 27 · ~1½ h
Part VII coda · the continuous cousin
-
29
Convexity, gradients, and what continuity changes
Gradients and momentum, projections and linear oracles, and the KKT conditions, which turn out to be the LP duality you already own.
slides · reading mode · interactive figuresneeds 03 (and 02) · ~1½ h
-
30
Automatic differentiation
Dual numbers and forward mode, the tape and reverse mode, why a full gradient costs one backward pass, what it costs in memory, and where the answers quietly stop being derivatives.
slides · reading mode · interactive figuresneeds 29, 28 · ~1½ h
-
31
Where discrete meets differentiable
Every decision in this course is an argmax. Four ways to get a useful gradient through one, and an honest test of whether learning helps inside an exact solver.
slides · reading mode · interactive figuresneeds 30, 07, 15 · ~1½ h
Capstone everything converges
-
∗
One problem, four traditions
Vehicle routing with time windows, solved by branch-and-cut, branch-and-price, CP-SAT and ALNS, then refereed on Solomon's instances with unit 28's method.
slides · reading mode · interactive figuresneeds 07, 08, 10, 18–19, 26, 28 · ~1¼ h