Downloads¶
The lecture notes, the exercise books and the catalogue of problems in PDF, with the same numbering of definitions, theorems, examples and exercises as the website, and the Colab notebooks with the code of the algorithms. Text and figures are released under CC BY 4.0, the code under the MIT licence.
Lecture notes¶
| Volume | Contents | Chapters | File |
|---|---|---|---|
| 1. Combinatorial optimization problems | Combinatorial optimization problems and their families: knapsack, packing, coloring, clique, routing, scheduling and lot sizing problems. For each problem: definition, assumptions, instances, counting the solutions, a first solution by hand and a simple bound. | 1–8 | PDF (0.8 MB) |
| 2. Formulations and their properties | Integer linear programming models of the problems of Volume 1, their linear programming relaxations and duals, the bounds they give, and the comparison between weaker and stronger formulations. | 9–15 | PDF (1.0 MB) |
| 3. Dynamic programming | The principles of dynamic programming and DP algorithms for knapsack problems, lot sizing, coin change and rod cutting: recurrences, pseudocode, complexity and worked tables. | 16–28 | PDF (1.3 MB) |
| 4. Heuristic algorithms | Heuristic algorithms: constructive heuristics, local search, metaheuristics and MIP-based heuristics, applied to the problems of the course. | 29–33 | PDF (1.7 MB) |
| 5. Approximation algorithms | Approximation algorithms: performance ratios and approximation schemes, with algorithms and worst-case analyses for knapsack, bin packing, the metric TSP and parallel machine scheduling, and the limits of approximation for vertex coloring, maximum clique and the general TSP. | 34–40 | PDF (1.1 MB) |
| 6. Ad hoc algorithms | Ad hoc algorithms: the branch-and-bound on the critical item for the 0/1 knapsack problem and the DSATUR branch-and-bound for vertex coloring. | 41–42 | PDF (0.5 MB) |
Exercise books¶
| Volume | Contents | Chapters | File |
|---|---|---|---|
| 1. Combinatorial optimization problems | Combinatorial optimization · Knapsack problems · Packing problems · Coloring problems · Clique problems · Routing problems · Scheduling problems · Lot sizing problems | 1–8 | PDF (0.6 MB) |
| 2. Formulations and their properties | Knapsack problems · Packing problems · Coloring problems · Clique problems · Routing problems · Scheduling problems · Lot sizing problems | 9–15 | PDF (0.6 MB) |
| 3. Dynamic programming | Principles · Knapsack problems · Lot sizing problems · Miscellaneous problems | 16–28 | PDF (1.0 MB) |
| 4. Heuristic algorithms | Definitions · Constructive heuristics · Local search · Metaheuristics · MIP heuristics | 29–33 | PDF (0.7 MB) |
| 5. Approximation algorithms | Principles · Knapsack problems · Packing problems · Coloring problems · Clique problems · Routing problems · Scheduling problems | 34–40 | PDF (0.7 MB) |
| 6. Ad hoc algorithms | Knapsack problems · Coloring problems | 41–42 | PDF (0.5 MB) |
Slides¶
The lecture slides, one PDF per chapter, with the same definitions and examples as the lecture notes.
Catalogue of problems¶
| Contents | File | |
|---|---|---|
| Catalogue of combinatorial problems | All the problems defined in the course, grouped by family: for each one its definition, its assumptions and what the course does on it, technique by technique. | PDF (0.6 MB) |
Colab notebooks¶
The code of the chapters on algorithms, one notebook per chapter and per language, to run in Google Colab or to download (.ipynb links). How to use them: the notebooks page.
