The problems at a glance¶
The course solves 7 combinatorial optimization problems in every way: their characteristics, what the course does on each one, and its catalogue page.
Characteristics¶
| Problem | A solution is | Objective | Constraints | Complexity |
|---|---|---|---|---|
| 0/1 knapsack problem (KP) | a subset of items | maximum total profit | total weight at most \(c\) | weakly NP-hard, pseudo-polynomial DP in \(O(nc)\) |
| Bin packing (BPP) | a partition of the items into bins | minimum number of bins | load of each bin at most \(c\) | strongly NP-hard |
| Vertex coloring (VCP) | a partition of the vertices into stable sets | minimum number of colors \(\chi(G)\) | adjacent vertices with different colors | strongly NP-hard |
| Maximum clique (MCP) | a subset of vertices | maximum cardinality \(\omega(G)\) | pairwise adjacent vertices | NP-hard |
| Travelling salesman (TSP) | a cyclic ordering of the cities | minimum tour length | each city visited exactly once | strongly NP-hard |
| Parallel machine scheduling (P||Cmax) | an assignment of jobs to machines | minimum makespan \(C_{\max}\) | each job on one machine, without interruption | strongly NP-hard (\(m\) part of the input) |
| Capacitated lot sizing (CLS) | setup periods and production quantities | minimum setup, production and holding cost | demand satisfied, capacities respected | NP-hard (the uncapacitated case is polynomial) |
What the course does on each problem¶
Each cell links to the chapter.
| Problem | Definition | Formulations | DP | Heuristics | MIP heuristics | Approximation | Ad hoc algorithms | Exercises |
|---|---|---|---|---|---|---|---|---|
| KP | Ch. 2 | Ch. 9 | Ch. 17, 18, 19, 20, 21, 22, 23, 24 | Ch. 30, 31, 32 | Ch. 33 | Ch. 34, 35 | Ch. 41 | Ch. 2, 9, 16, 17, 29, 30, 31, 32, 33, 34, 35, 41 |
| BPP | Ch. 3 | Ch. 10 | — | Ch. 30, 31, 32 | Ch. 33 | Ch. 30, 36 | — | Ch. 1, 3, 10, 29, 30, 31, 32, 34, 36 |
| VCP | Ch. 4 | Ch. 11 | — | Ch. 30 | — | not approximable | Ch. 42 | Ch. 4, 11, 30, 37, 42 |
| MCP | Ch. 5 | Ch. 12 | — | Ch. 5 | — | not approximable | — | Ch. 4, 5, 12, 38 |
| TSP | Ch. 6 | Ch. 13 | — | Ch. 6, 30, 31, 32 | Ch. 33 | Ch. 39 | — | Ch. 1, 6, 13, 29, 30, 31, 32, 39 |
| P | Cmax | Ch. 7 | Ch. 14 | — | Ch. 30, 31, 32 | Ch. 33 | Ch. 34, 40 | |
| CLS | Ch. 8 | Ch. 15 | Ch. 26 | Ch. 8, 33 | Ch. 33 | — | — | Ch. 8, 15, 26 |
The catalogue pages¶
- 0/1 knapsack problem (KP) — what the course does on this problem
- Bin packing (BPP) — what the course does on this problem
- Vertex coloring (VCP) — what the course does on this problem
- Maximum clique (MCP) — what the course does on this problem
- Travelling salesman (TSP) — what the course does on this problem
- Parallel machine scheduling (P||Cmax) — what the course does on this problem
- Capacitated lot sizing (CLS) — what the course does on this problem