Self-study curriculum · proposal · 2026-09-12 · times updated 2026-09-15
Combinatorial & Constrained Optimization
Thirty-two units in which every piece of theory is cashed out as something you
implement, and every implementation is then beaten by a real solver so you can
see exactly what the theory you skipped was worth.
32units
~155 hslides + labs
3trunks
~40from-scratch builds
7parts + capstone
0fixed deadlines
The premise
Three things shape this curriculum, and all three came out of your answers.
You are past the fundamentals but not at the frontier. So the course does
not teach you what a proof is or re-derive Gaussian elimination. It starts at
polyhedra, spends one unit longer than feels necessary on duality — because
duality is the single idea that cutting planes, column generation, Lagrangian
relaxation, the Hungarian algorithm, primal–dual approximation and KKT are all
special cases of — and then moves fast.
From scratch, then solvers. Each unit has you build the naive thing, then
run the industrial thing on the same instance and measure the gap. This is the
only honest way to learn why branch-and-cut has the shape it has: you write a
branch-and-bound, watch CBC beat it by 400×, and then spend the next unit finding
out which of its features was worth how much. The comparison is not decoration —
it is the assessment.
No calendar, so this is a dependency graph. Units say what they need, not
when they happen. There are three trunks descending from a common root — the
polyhedral line (LP → IP), the combinatorial line (matroids, flows, matching, DP)
and the constraint line (CP, SAT) — and they are genuinely independent for a long
way. You can put one down for two months and pick up another. They converge only
when you get to approximation, where you need all three.
What a unit is
Every unit is the same four things. A unit is done when the checkpoint is true —
not when you have read the chapter.
Theory
The named results and algorithms, with the reading that covers them. Roughly
the size of one book chapter.
Build
Python, from scratch, no optimization library. Correctness checked
differentially against the brute-force oracle you write in unit 00.
Then
The same instances through HiGHS / Gurobi / OR-Tools / CaDiCaL. Record the
gap. The gap is the lesson.
Checkpoint
A single falsifiable claim about what you can now do. If you cannot make it
true, the unit is not finished — and you know precisely what is missing.
How long. Each unit's title slide gives its own estimate, typically
1½–2 h of slides and 2–3 h of lab. Summed over all units that is about 57 h of
slides and 96–99 h of labs, the capstone's 12–15 h included: roughly
155 hours in all. Take it as a scale, not a schedule.
The shape of it
Solid arrows are prerequisites. Dashed arrows are the cross-trunk links — the
places where one tradition turns out to need another, which are the most
interesting moments in the course.
linear programminginteger programmingcombinatorial algorithmsconstraints & SAThardness & approximationpracticecontinuous & ML codacross-trunk link
Part 0 — the ground floor
One unit, and you will use it in all thirty-one others
The single most common way self-study in this field goes wrong is having no way
to tell whether the clever thing you just wrote is correct. Fix that first.
00
Models, instances, and an oracle you trust
spine
needsnothing
Theory
What makes a problem combinatorial: a finite feasible set described
implicitly by constraints. Decision vs optimization vs counting. Certificates
and why "here is the answer" and "here is why nothing is better" are different
objects. The nine problems you will return to all course: knapsack, set cover,
assignment, bin packing, graph colouring, max-cut, TSP, job-shop scheduling,
vertex cover.
Build
An instance library — generators plus readers for the formats the field
actually trades in (DIMACS .cnf, TSPLIB, MIPLIB .mps) — and a
brute-force enumerator. Then a differential test harness: every algorithm you
write from here on is run against the enumerator on small instances, and
disagreement fails loudly with the offending instance printed.
Then
Nothing yet. This unit is the measuring stick, not a thing to be measured.
Checkpoint. You can generate a random instance of any of the
nine problems, solve it exactly by enumeration up to n ≈ 20, and your harness
catches a deliberately broken algorithm without you looking for it.
Part I — trunk A begins · linear programming and duality
The continuous shadow that every discrete algorithm reasons about
Nothing here is combinatorial yet. It is all load-bearing anyway: integer
programming is the study of what happens when you take the LP relaxation
seriously, and you cannot do that without knowing what the relaxation is.
Polyhedra as intersections of halfspaces; the equivalence of vertex, extreme
point and basic feasible solution; Minkowski–Weyl (V- and H-representations);
Fourier–Motzkin elimination and its blow-up; Farkas' lemma and the idea of an
infeasibility certificate; the fundamental theorem of linear programming.
Build
A Fourier–Motzkin eliminator (and watch the constraint count explode). Vertex
enumeration of a small polytope by brute-force basis enumeration — which ties
straight back to unit 00's enumerator. A Farkas certificate checker.
Then
scipy.spatial.ConvexHull and pycddlib to cross-check your
V↔H conversions.
Checkpoint. Given an infeasible system you can produce the
Farkas vector and explain, without reference to any solver, why it constitutes a
proof of infeasibility.
The tableau and the revised simplex; pivoting as a walk on vertices; Dantzig's
rule, Bland's anti-cycling rule, degeneracy and stalling; two-phase and big-M
starts; Klee–Minty and the embarrassment of a worst-case-exponential algorithm
that is the workhorse of the field; why real implementations use LU factorisation
with periodic refactorisation and steepest-edge pricing.
Build
A dense tableau simplex with pluggable pricing. Reproduce Beale's cycling
example and watch Bland's rule fix it. Write a Klee–Minty generator and plot
pivot count against dimension — the exponential is visible by n = 12.
Then
scipy.optimize.linprog (HiGHS). Compare iteration counts and find the
instance family where your numerics fall apart first.
Checkpoint. Your simplex agrees with HiGHS on 1000 random LPs,
you can exhibit an instance where yours cycles without Bland's rule, and you can
say in one sentence what steepest-edge pricing buys over Dantzig's rule.
The dual as a mechanical transform of the primal; weak and strong duality;
complementary slackness; duals as shadow prices; the dual simplex and why it is
the algorithm that makes branch-and-cut possible; sensitivity analysis and
ranging. Spend longer here than feels justified: units 08, 10, 11, 12, 15, 24 and
29 are each this unit wearing a different hat.
Build
An automatic primal→dual transformer that handles all constraint senses and
variable bounds. Extract dual values from your simplex basis and verify
complementary slackness numerically. Implement the dual simplex and use it to
re-solve after adding one constraint — the warm start that branch-and-cut lives
on.
Then
Pull duals and reduced costs out of HiGHS and Gurobi; confirm yours match,
including sign conventions (which will take you an afternoon, and should).
Checkpoint. Given a solved LP you can read off the shadow price
of each constraint, predict the objective change from a small right-hand-side
perturbation before re-solving, and be right.
Why "is LP in P?" was open until Khachiyan in 1979; the ellipsoid method's
volume-shrinking argument; why it is useless in practice and indispensable in
theory (see unit 09); Karmarkar and the primal–dual path-following interior point
method; the central path and the log barrier; why IPMs win on large sparse LPs and
lose badly on warm starts.
Build
A log-barrier method on two-variable LPs with the central path plotted — this
is a picture worth having. A toy ellipsoid method for feasibility.
Then
HiGHS or Gurobi with method=barrier vs simplex on a large sparse LP;
find the crossover size. Then re-solve with one constraint added and watch the
barrier method lose.
Checkpoint. You can choose between simplex and barrier for a
given LP and defend it, and explain why branch-and-bound still wants simplex at
every node.
Part II — trunk A continues · integer programming
Where hardness enters, and the architecture that copes with it
The longest part, and the one that most repays the slow reading. Everything here
is a strategy for exploiting the LP relaxation you built in Part I: tighten it,
branch on it, cut it, decompose it, or dualise it.
05
Formulations, relaxations, and the integrality gap
IP and MIP; the LP relaxation; the convex hull of integer points as the ideal
formulation you can never write down; formulation strength as a partial order;
big-M versus indicator constraints, and how a lazily chosen M destroys solve
times; extended formulations and the power of auxiliary variables — with the
Fiorini–Massar–Pokutta–Tiwary–de Wolf result that no polynomial-size extended
formulation of the TSP polytope exists; symmetry as a formulation defect.
Build
Three formulations of one facility-location instance family — weak big-M,
tight big-M, and disaggregated. Measure the root relaxation bound of each. Keep
them; units 07, 08 and 27 come back to these same three models.
Then
CBC and Gurobi through PuLP or python-mip. Tabulate relaxation gap, node
count, and wall time for all three. The ordering will be stark.
Checkpoint. Shown two formulations of one problem, you can
predict which solves faster from their relaxation bounds alone, and be right more
often than not.
Totally unimodular matrices; the Hoffman–Kruskal theorem; interval matrices,
network matrices, bipartite incidence matrices; why assignment, transportation and
flow LPs have integral optima with no branching at all; balanced and perfect
matrices; integral polyhedra in general. This unit explains why Part III exists
— the polynomial islands are the places where the LP is already integral.
Build
A TU checker using Ghouila-Houri's criterion on small matrices. Solve an
assignment problem as a pure LP and watch integrality fall out unasked. Then make
the graph non-bipartite and watch half-integral vertices appear.
Then
LP-solved assignment vs scipy.optimize.linear_sum_assignment.
Checkpoint. Given a constraint matrix you can decide whether to
expect integral LP optima, and when the answer is no, construct the odd cycle that
breaks it.
The search tree; bounding and pruning; branching variable selection —
most-fractional, pseudocost, strong branching, reliability branching; node
selection — depth-first for incumbents, best-first for the bound, and the hybrids
everyone actually ships; primal heuristics (diving, RINS, feasibility pump); the
gap; why the two hard jobs are finding a good solution early and proving
nothing better exists.
Build
Your own branch-and-bound over your unit-02 simplex, with pluggable branching
and node selection and instrumented node counts. Run the full matrix
{most-fractional, pseudocost, strong} × {DFS, best-first} on the unit-05
formulations.
Then
CBC and Gurobi on the same instances. Read their logs line by line, find your
factor of shame in node count, and write down which of their features you believe
explains it. Units 08 and 27 then test those hypotheses.
Checkpoint. Your strong-branching variant beats your
most-fractional variant on node count while losing on wall time, and you can
explain that trade-off in terms of LP solves per node.
Valid inequalities, faces and facets; Chvátal–Gomory cuts and CG rank; Gomory
mixed-integer cuts read straight off the simplex tableau; the problem-specific
families that do the real work — knapsack cover cuts and lifting, clique and
odd-hole cuts, flow covers, MIR; the separation problem as the central question;
cut management, and why solvers discard most cuts they generate;
branch-and-cut as the actual architecture of every modern MIP solver.
Build
Gomory fractional cuts from your tableau, applied at the root until the
tableau's numerics defeat you (they will — that is a finding, not a failure).
Cover-cut separation for knapsack, with lifting. A cut pool with an aging policy.
Report gap closed at the root per family.
Then
Gurobi with Cuts=0 vs default; compare your root gap closed against
theirs, per cut family where the log tells you.
Checkpoint. From a fractional simplex tableau you can write down
a valid Gomory cut by hand and prove it separates the current vertex while
excluding no integer point.
The Grötschel–Lovász–Schrijver equivalence: you can optimize over a polytope
in polynomial time if and only if you can separate over it in polynomial time,
with the ellipsoid method as the bridge. Why this makes exponentially many
constraints perfectly acceptable — subtour elimination for TSP, the odd-set
inequalities of the matching polytope — and why lazy constraints are the
engineering face of a theorem. This is the most beautiful result in the course.
Build
A subtour-elimination separation oracle: connected components for integral
points, min-cut (your unit-14 max-flow, if you have it) for fractional ones. Solve
the TSP relaxation by lazy constraint generation and watch a few hundred
constraints stand in for 2n.
Then
Gurobi lazy-constraint callbacks on TSPLIB instances of a few hundred cities.
Then Concorde, to see what a decade of this idea looks like.
Checkpoint. You can state the theorem precisely, and you have
solved a TSP over an exponential constraint family while only ever writing down a
few hundred of its constraints.
The restricted master problem; reduced costs and the pricing subproblem;
Dantzig–Wolfe decomposition and block-angular structure; why the pricer is usually
itself NP-hard and that is fine; the Lagrangian bound you get for free; dual
degeneracy and stabilisation; branch-and-price, and why naive variable branching
destroys the pricing problem.
Build
Cutting stock by column generation with a knapsack pricer (your unit-16 DP,
reused). Then vehicle routing, where pricing becomes a resource-constrained
shortest path — the step where this stops being a toy.
Then
The compact MIP formulation of the same cutting-stock instance in Gurobi.
Compare bound quality and model size; the point at which the compact model stops
fitting in memory is the argument for the whole technique.
Checkpoint. You can explain why the master's dual values are
exactly the objective coefficients of the pricing problem, in the vocabulary of
unit 03, without hand-waving.
Dualising the hard constraints; the Lagrangian dual and its concavity; the
integrality property — and why it tells you in advance when Lagrangian
relaxation will give you nothing the LP did not; subgradients and step-size rules;
the Held–Karp bound for TSP via 1-trees; Lagrangian heuristics and variable fixing
by reduced cost.
Build
The Held–Karp 1-tree bound with subgradient ascent, on TSPLIB instances. A
Lagrangian relaxation of generalised assignment, with the bound tracked against
iteration count so you can see the notorious zig-zag.
Then
Compare your Held–Karp bound to Gurobi's root LP bound on the same instances.
They should be close, and knowing why they are close is the unit.
Checkpoint. Before writing any code, you can predict whether
dualising a given constraint set will beat the LP relaxation, using the
integrality property.
Splitting a MIP into a master over the hard variables and a subproblem over
the rest; optimality and feasibility cuts derived from the subproblem's dual;
Benders as row generation and therefore the formal dual of Dantzig–Wolfe's column
generation; two-stage stochastic programming with recourse as its natural home;
modern variants — Benders inside the branch-and-bound tree, cut strengthening,
Pareto-optimal cuts.
Build
Benders on a two-stage stochastic facility location, with the scenario
subproblems solved independently.
Then
The monolithic deterministic-equivalent model in Gurobi. Find the scenario
count at which Benders overtakes it — then report it as a crossover plot, not an
anecdote.
Checkpoint. You can draw Dantzig–Wolfe and Benders on one page
as duals of each other — rows vs columns, master vs subproblem — and point at
where unit 03 sits in both.
Part III — trunk B · the polynomial islands
The problems that are genuinely easy, and the structural reasons why
Independent of Parts I–II: you can start this trunk the day after unit 00. But
read unit 06 alongside it — total unimodularity is the polyhedral explanation for
everything that happens here.
Independence systems and matroids; the exchange axiom; the Rado–Edmonds
theorem — greedy is optimal on a matroid and only on a matroid, which is the
cleanest "when does this heuristic actually work" answer in the field; graphic,
linear, uniform, partition and transversal matroids; matroid intersection in
polynomial time and three-matroid intersection in NP-hard; submodularity, the
1 − 1/e greedy bound for monotone submodular maximisation, and the matroid
polytope.
Build
A matroid interface with independence oracles; instantiate the graphic matroid
and watch Kruskal's algorithm fall out of generic greedy. Matroid intersection.
Greedy submodular maximisation on a coverage function, with the 1 − 1/e bound
checked empirically against exact optima from unit 00.
Then
networkx MST for the graphic case; an exact MIP for small submodular
instances.
Checkpoint. Shown a greedy algorithm someone proposes, you can
either name the matroid underneath it or construct the instance where it fails.
Max-flow min-cut; augmenting paths; Ford–Fulkerson's failure to terminate on
irrational capacities; Edmonds–Karp, Dinic, push–relabel and their complexities;
min-cost flow by successive shortest paths with potentials, cycle cancelling, and
network simplex; flow decomposition. The real skill is reduction to flow:
bipartite matching, project selection / maximum closure, image segmentation,
baseball elimination, and scheduling with deadlines.
Build
Dinic and push–relabel; min-cost flow by SSP with Johnson potentials; the
project-selection reduction end to end.
Then
OR-Tools SimpleMaxFlow / SimpleMinCostFlow and
networkx. Benchmark on layered vs random vs bipartite graphs and find the
family where push–relabel beats Dinic.
Checkpoint. Handed a problem you have not seen, you can decide
whether it is a flow in disguise and write the reduction, including the capacities
that encode the objective.
König's and Hall's theorems on bipartite graphs; Hopcroft–Karp; the
Hungarian algorithm as primal–dual on the assignment LP — the first place unit 03
pays off outside LP; Tutte's theorem; Edmonds' blossom algorithm and the paper
that first argued "polynomial" is the right definition of tractable; the matching
polytope's odd-set inequalities (which is unit 09's other example); Gale–Shapley
stable matching as a different beast entirely.
Build
Hopcroft–Karp. The Hungarian algorithm from scratch, printing its dual
potentials. Blossom as the stretch goal — it is hard, and worth one difficult
week. Gale–Shapley, for contrast.
Checkpoint. You can verify your Hungarian algorithm's answer is
optimal by checking complementary slackness against its dual potentials, without
re-running the algorithm.
DP as shortest path in a DAG of states; knapsack's pseudo-polynomial algorithm
and precisely why it does not contradict NP-hardness; bitmask DP; Held–Karp
exact TSP in O(n²2ⁿ); DP on trees; treewidth and tree decompositions; Courcelle's
theorem as the general statement of why all of these work; the vocabulary of
parameterised complexity — FPT, XP, kernelisation — as the honest way to say "hard
but not hopeless".
Build
Knapsack DP (this becomes unit 10's pricer). Held–Karp exact TSP. A
tree-decomposition DP for vertex cover, with runtime plotted against treewidth on
random graphs — the exponential in the parameter, made visible.
Then
Held–Karp against your unit-07 branch-and-bound and against Gurobi on
n = 15…22 — three completely different algorithms, one crossover plot.
Checkpoint. You can compute a decomposition's width and predict
the DP's runtime from it to within an order of magnitude.
Part IV — trunk C · constraint programming and SAT
The other tradition: prune the domain rather than relax and bound
A genuinely different intellectual lineage, with different vocabulary and
different instincts — and the one that currently wins scheduling competitions
outright. Independent of Parts I–II except where marked.
The CSP as a formalism — variables, domains, constraints, often no objective at
all; consistency levels (node, arc, path, k-consistency) and what each costs;
AC-3 and AC-4; bounds vs domain consistency; propagation to a fixpoint;
backtracking search interleaved with propagation as the CP loop. The
philosophical difference from Part II stated plainly: MIP relaxes and bounds, CP
prunes domains, and the two see completely different instances as easy.
Build
A small CP engine: domains with trailing, a propagation queue, AC-3,
backtracking search. Solve Sudoku, n-queens, map colouring, magic series — and
instrument propagations and nodes, because those two numbers are the whole
diagnostic vocabulary of Part IV.
Then
OR-Tools CP-SAT on the same models.
Checkpoint. You can trace your propagator's fixpoint by hand on
a 4×4 Sudoku, and explain why arc consistency does not imply satisfiability.
Why one constraint over n variables beats n(n−1)/2 binary ones; Régin's
filtering foralldifferent, via Hall sets and maximum matching in the
value graph — which is unit 15 doing load-bearing work in a different tradition;
cumulative with timetable and edge-finding filters, and disjunctive
scheduling; element, table, circuit,
gcc; the trade-off between a propagator's strength and its
cost, which is the only design question in CP.
Build
Régin's alldifferent on top of your Hopcroft–Karp. A
cumulative timetable propagator. Plug both into your unit-17 engine and
measure the node-count collapse on n-queens and job-shop.
Then
CP-SAT's AddAllDifferent and AddCumulative on the same
models.
Checkpoint. On one instance, your decomposed model and your
global-constraint model give the same answer and differ by orders of magnitude in
node count — and you can name the Hall set responsible.
Variable ordering (first-fail, dom/wdeg, impact-based) and value ordering;
symmetry breaking during search; randomisation and restart policies, Luby in
particular; nogood recording; heavy-tailed runtime distributions and why they
are the actual justification for restarts; large neighbourhood search — destroy
and repair, with the propagator as the repair engine — as the bridge from exact
search to heuristics.
Build
dom/wdeg and impact-based heuristics in your engine; Luby restarts; run 100
seeds on one hard instance and plot the runtime distribution until you can see the
heavy tail. Then an LNS layer on job-shop.
Then
CP-SAT with its LNS workers disabled and enabled; OR-Tools' routing solver on
a CVRP.
Checkpoint. You can show the heavy-tailed runtime histogram from
your own solver and demonstrate that restarts move its mean — with the
distributions, not with one lucky run.
CNF, resolution, DPLL; unit propagation; conflict analysis via the implication
graph and the first-UIP cut; clause learning and non-chronological backjumping;
VSIDS activity heuristics; two-watched-literal propagation; clause deletion and
LBD; phase saving. Then the honest framing: CDCL is resolution with a very good
heuristic, and proof complexity tells you exactly what it can never do quickly.
Encodings: Tseitin, at-most-one (pairwise, sequential, commander, bitwise),
cardinality networks.
Build
A CDCL solver — watched literals, 1UIP learning, VSIDS, Luby restarts,
LBD-based clause deletion. Then encoders for graph colouring, n-queens, and the
pigeonhole principle, which will humiliate it. That humiliation is the unit's
point.
Then
MiniSat, CaDiCaL and Kissat on your CNFs. DIMACS in and out, so instances
travel both ways.
Checkpoint. Your solver emits a DRAT proof that an external
checker accepts, and you can explain pigeonhole's hardness in terms of resolution
lower bounds rather than "it just takes a long time".
21
Lazy clause generation, or what CP-SAT actually is
The hybrid that ate the field: CP propagators that explain their inferences
as clauses, fed to a CDCL engine that learns from them; the order encoding of
integers that lets a SAT solver reason about bounds; SMT and DPLL(T) as the same
idea arriving from the other direction; the linear relaxation CP-SAT runs
alongside, which is Part II smuggled into Part IV.
Build
Make one unit-18 propagator explanation-producing and feed its clauses to your
unit-20 CDCL. Measure what learning from propagation buys on job-shop.
Then
Read CP-SAT's log on a job-shop instance and identify, by name, every component
you have now built yourself.
Checkpoint. For a problem you have not modelled before you can
say which of MIP / CP / SAT / CP-SAT you would reach for first, and defend it with
something other than taste.
Part V — where the trunks converge
When exact is hopeless: how far from optimal must you settle?
This is the part that needs all three trunks — LP for rounding, matching and MST
for Christofides, CP for the neighbourhood search. It is also the part with the
most beautiful theory in the whole subject.
NP-completeness through the canonical reduction chain (3SAT → vertex cover →
set cover → …); strong vs weak NP-hardness, and why knapsack sits on the weak
side; the approximation hierarchy — FPTAS ⊂ PTAS ⊂ APX ⊂ log-approximable ⊂ the
rest; the PCP theorem's role in making hardness of approximation possible;
Set Cover's (1−o(1))·ln n threshold; Vertex Cover's 2−ε and Max-Cut's 0.878 under
the Unique Games Conjecture. The practical payoff: knowing when to stop looking
for a better algorithm.
Build
Mechanised reductions — a program that maps a 3SAT instance to a vertex cover
instance and maps solutions back, verified against your unit-00 oracle in both
directions. Reductions become much less abstract once yours has a bug.
Then
Solve both sides of each reduction with CP-SAT and confirm optimality is
preserved, not just feasibility.
Checkpoint. For each of unit 00's nine problems you can state
the best known approximation ratio and the best known hardness bound, and say
where the gap is still open.
Greedy set cover's Hn bound and its tightness; 2-approximation for
vertex cover via maximal matching; metric TSP — double-tree 2-approximation,
Christofides at 3/2, and the 2021 Karlin–Klein–Oveis Gharan improvement that
finally broke it; k-center greedy and its 2-tightness; local search for k-median;
scheduling — list scheduling's 2−1/m, LPT's 4/3, and the FPTAS for makespan on a
fixed number of machines.
Build
Greedy set cover with the Hn bound checked empirically. Christofides
— which needs your MST from unit 13 and your minimum-weight perfect matching from
unit 15, and is the moment trunk B pays off. LPT. k-center greedy.
Then
Measure actual ratios against CP-SAT-proved optima on instances small enough
to solve exactly. The distance between worst-case guarantee and typical
performance is the finding.
Checkpoint. Your Christofides never exceeds 1.5× optimum on
instances you can solve exactly, and you can point at the line of code
corresponding to each step of the proof.
Deterministic rounding (vertex cover's ½-threshold, which is a two-line proof
and a genuinely surprising one); randomized rounding with the Chernoff and
union-bound argument giving set cover's O(log n); the integrality gap as the
hard limit on any LP-based analysis; the primal–dual schema — raise duals, buy
primals, pay for what you bought — for set cover, Steiner forest and facility
location; iterative rounding and Jain's 2-approximation for Steiner network as the
elegant endpoint.
Build
Randomized rounding for set cover, with the failure probability measured
empirically against the bound. Primal–dual set cover. Primal–dual facility
location.
Then
Three numbers on every instance — the LP bound from HiGHS, the integer optimum
from Gurobi, and your rounded solution — plotted together. The visible gap between
the first two is the integrality gap you just read about.
Checkpoint. You can exhibit an instance realising the
integrality gap of a given LP, thereby proving no rounding of that LP can beat
that ratio.
Optimising over the PSD cone; vector programs as relaxations that LPs cannot
express; Goemans–Williamson Max-Cut and random-hyperplane rounding at 0.878…;
the Lovász theta function sandwiched between clique and chromatic number; the
Lasserre / Sum-of-Squares hierarchy as a tower of ever-tighter relaxations and the
lower bounds against it; why SDPs are convex but expensive, which is why they stay
a theoretical tool.
Build
Goemans–Williamson with CVXPY plus your own hyperplane rounding, over many
random hyperplanes. The theta function on small graphs. Compare the SDP bound, the
LP bound, and the truth on the same instances.
Then
Exact Max-Cut with Gurobi for n ≤ 40 to measure your realised ratio.
Checkpoint. You can show empirically that your GW cuts average
well above 0.878 of optimum, and explain why the guarantee is nonetheless
tight.
Local search and neighbourhood design; 2-opt, 3-opt, Or-opt and Lin–Kernighan
for TSP; simulated annealing and its cooling schedules; tabu search; GRASP;
iterated and adaptive large neighbourhood search; genetic algorithms, and a
frank account of why they are usually the wrong answer. Then the part most courses
omit: this literature has a replication problem, "our metaheuristic beat theirs"
is very often unfalsifiable, and knowing what an honest comparison requires is
more valuable than knowing a tenth metaphor.
Build
2-opt and Or-opt with don't-look bits and neighbour lists for TSP. Simulated
annealing with a tuned schedule. ALNS for CVRP with destroy/repair operators and
adaptive weights.
Then
LKH and OR-Tools routing on the same instances under the same time
budget — the constraint most published comparisons quietly drop.
Checkpoint. You can produce a time-to-target plot comparing
three of your own heuristics over 30 seeds, and correctly decline to declare a
winner where the distributions overlap.
Part VI — making it real
The two units that make every earlier claim defensible
Short, unglamorous, and the difference between having done a course and being able
to use any of it. Unit 28 in particular retroactively upgrades every "compare"
step you have run so far.
What presolve actually does, and the modelling habits that defeat it; symmetry
and symmetry breaking (lex-leader constraints, orbital branching) — the single
biggest lever on many models; indicator constraints instead of big-M; bound
tightening; warm starts and MIP starts; solution pools; and reading a solver log
fluently — the gap, node count, cut counts per family, heuristic hits, presolve
reductions. MIPLIB 2017 as the field's shared reality check.
Build
Take your worst-performing model from units 05 and 07 and make it 10× faster
without changing what it means. One intervention at a time, each measured
separately.
Then
Gurobi and HiGHS logs on MIPLIB instances — including a few that neither
solves, so the experience of a genuinely open instance is not theoretical.
Checkpoint. A before/after table of your own model with one row
per intervention and the time each bought, containing no row you cannot
explain.
Performance profiles (Dolan–Moré); the shifted geometric mean, and why the
arithmetic mean of solver times is close to meaningless; time-to-target plots for
stochastic algorithms; instance selection bias; per-instance versus aggregate
claims; seeds and variance; the virtual best solver as a reference point; and how
to report a negative result so it is still worth reading.
Build
A benchmarking harness — instance sets, timeouts, seeds, per-run records in a
queryable form, and the three plot types. Then re-run every algorithm from
units 02–26 through it and regenerate all your earlier comparisons properly.
Then
This is the unit where the earlier "then" steps get audited. Expect at least
one earlier conclusion not to survive; that is the unit working.
Checkpoint. Every performance claim in your notes regenerates
from one command, and each one survives the regeneration — or has been corrected
in place.
Part VII — coda · the continuous cousin
Autodiff, and the seam where discrete optimization meets modern ML
A deliberate skim, as you asked — three units, not a second course. But they are
placed at the end rather than the start on purpose: once you know LP duality and
branch-and-bound, KKT is a generalisation you already half-own, and "learning to
branch" is a sentence about something you built in unit 07 rather than a slogan.
Convex sets and functions; gradients and subgradients; the KKT conditions as
the generalisation of LP duality you already know — complementary slackness is
the KKT complementarity condition, and seeing that is most of the unit; first-order
methods (gradient descent, momentum, Nesterov) and their rates; stochastic
gradients; constrained methods — projected gradient, and Frank–Wolfe, which puts a
linear optimization oracle inside a continuous loop and is therefore the
cleanest formal handshake between the two halves of this course.
Build
GD, momentum and Nesterov on standard test functions with convergence plotted.
Projected gradient onto a simplex. Then Frank–Wolfe over a polytope, using your
unit-02 simplex as the linear oracle.
Then
scipy.optimize and CVXPY for the same problems.
Checkpoint. You can derive the KKT conditions for a linear
program and show they reduce exactly to complementary slackness from unit 03.
The three things constantly confused: symbolic, numerical and automatic
differentiation. Dual numbers and forward mode. The Wengert tape and reverse mode.
The one fact that explains modern ML's existence: reverse mode computes a full
gradient in O(1) forward passes regardless of parameter count, while forward mode
costs one pass per parameter. Checkpointing and the memory/compute trade.
Jacobian-vector and vector-Jacobian products; forward-over-reverse for
Hessian-vector products. And where autodiff quietly lies: non-smooth points,
control flow, in-place mutation, and argmax.
Build
Forward-mode AD with dual numbers. Then a reverse-mode tape with a small op
set — enough to train a two-layer MLP with your own backprop. Gradient-check every
op against finite differences.
Then
JAX or PyTorch: grad, jacrev, jacfwd. Confirm
your gradients agree to 1e-6, and time yours against theirs.
Checkpoint. Your reverse-mode engine trains an MLP on a real
dataset, and you can compute the tape's memory cost in bytes before you run it.
Differentiating through discrete choices — straight-through estimators,
Gumbel-Softmax and concrete relaxations, REINFORCE versus reparameterisation.
Differentiable optimization layers: differentiating through an argmin via the
implicit function theorem applied to the KKT conditions (OptNet, cvxpylayers),
differentiable sorting and top-k, and Sinkhorn as a differentiable relaxation of
the assignment problem — your unit-15 Hungarian algorithm, softened. Then
learning to optimize: learned branching and cut-selection policies inside MIP
solvers, neural combinatorial optimization (pointer networks, attention models,
POMO), and the honest current state — still behind LKH and CP-SAT on classical
problems, genuinely promising as guidance inside exact solvers rather than as a
replacement for them.
Build
Sinkhorn against your Hungarian algorithm on the same assignment instances —
accuracy, speed, and the gradient the Hungarian cannot give you. Then a learned
branching rule for your unit-07 branch-and-bound, trained by imitating strong
branching, evaluated on node count over held-out instances.
Then
cvxpylayers for the argmin layer; optionally a pretrained attention
TSP model against LKH, which is a bracing comparison.
Checkpoint. Your imitation-learned branching rule beats
most-fractional branching on node count on held-out instances — or you can say
precisely why it did not, in terms of unit 28's methodology rather than
anecdote.
Capstone — one problem, four traditions
Everything converges on a single instance family, which you attack four ways and
then referee.
The brief
Pick one problem — capacitated vehicle routing with time windows, or job-shop
scheduling. Then solve it four times: (a) a MIP with your own cover and
subtour cuts on a commercial solver; (b) branch-and-price with a
resource-constrained shortest-path pricer; (c) CP-SAT with global
constraints and a search strategy you chose deliberately; (d) ALNS with
operators you designed.
Then run all four through your unit-28 harness on a shared instance set under a
shared time budget, and write the report that says which wins where. The
deliverable is not a winner — it is a defensible account of which instance
characteristics favour which method, with the evidence attached and the cases
where the answer is "they are indistinguishable" reported as such.
If thirty-two is too many
There is a defensible short path. It drops every branch node and all of trunk C's
depth, and it still leaves you able to read the literature.
Add 30 for the autodiff skim. What you lose: the decompositions
(10–12), all the approximation theory (22–25), and the matroid framing that makes
greedy make sense. What you keep: the ability to model a problem, choose a
paradigm, implement the core algorithm of each, and benchmark the result
honestly.
Reading and tools
Chosen so that most units have exactly one chapter to read, not four books to
triangulate between.
Primary texts
Bertsimas & Tsitsiklis, Introduction to Linear Optimization — Part I. The best treatment of duality for someone who wants to actually use it.
Wolsey, Integer Programming (2nd ed.) — Part II, readable end to end.
Conforti, Cornuéjols & Zambelli, Integer Programming — Part II when you want the modern, deeper account.
Korte & Vygen, Combinatorial Optimization — Part III's reference, and the book to own.
Williamson & Shmoys, The Design of Approximation Algorithms — the whole of Part V. Free PDF from the authors.
Rossi, van Beek & Walsh, Handbook of Constraint Programming — Part IV.
Biere, Heule, van Maaren & Walsh, Handbook of Satisfiability — units 20–21.
Worth having nearby
Schrijver, Theory of Linear and Integer Programming — consulted, not read.
Papadimitriou & Steiglitz, Combinatorial Optimization — cheap Dover, excellent on the classics.
Gärtner & Matoušek, Understanding and Using Linear Programming — short and very good.
Griewank & Walther, Evaluating Derivatives — unit 30's actual source.
Baydin et al., Automatic Differentiation in Machine Learning: a Survey — the 30-page version.
Bengio, Lodi & Prouvost, Machine Learning for Combinatorial Optimization — unit 31's survey.
Solvers and libraries
HiGHS — open LP/MIP, and what SciPy calls underneath.
SCIP — open branch-and-cut whose source is genuinely readable; the best way to check what you built in unit 07.
Gurobi — free academic licence; the reference for "how fast should this be".
OR-Tools CP-SAT — Part IV's target, and the thing unit 21 explains.
PuLP / python-mip — modelling layers.
CaDiCaL, Kissat, MiniSat — unit 20.
Concorde, LKH — the TSP reality checks.
NetworkX, CVXPY, JAX — Parts III, V and VII.
What this proposal still needs from you
Four open questions. None of them blocks starting unit 00.
Open
Which branches stay. Units 04, 06, 09, 12, 21 and 25 are optional. Unit 09 is the one I would fight to keep; unit 12 is the one I would cut first.
The capstone problem. CVRPTW has better instance libraries and a richer literature; job-shop shows CP-SAT at its most dominant. Picking now changes which examples I use from unit 07 onward.
Where the notes live. One Markdown file per unit, or a dear-guide graph where each checkpoint is a task with its falsifier. The second fits how the rest of this workshop already records things.
Gurobi licence. Several "then" steps assume one. If not, SCIP substitutes everywhere with a small loss of speed and no loss of pedagogy.
Deliberately excluded
Nonlinear and mixed-integer nonlinear programming. A second course, not a section.
Robust and stochastic optimization beyond unit 12's two-stage example.
Online and streaming algorithms — competitive analysis is a different discipline.
Quantum and Ising-machine approaches. Unit 28's methodology is the right lens on those claims, and unit 28 is enough.
A deep-learning course. Part VII skims deliberately; it exists to connect what you built to what you already know, not to teach ML.