Selected problems¶
Part 1 of the course, volume 1 of the lecture notes: chapters 2–8.
The families of problems on which the whole course focuses: each family opens with an overview, then one page per problem with its definition, its assumptions and a first example.
Lecture notes (PDF) Exercises (PDF) The problems at a glance
-
2. Knapsack problems
Choose items of maximum total profit within the capacity: the 0/1 knapsack problem, subset sum, the bounded and unbounded knapsack problems, and more.
0/1 knapsack (KP) · Subset sum (SSP) · Bounded knapsack (BKP) · Unbounded knapsack (UKP) · Multidimensional knapsack (MDKP) · Multiple knapsack (MKP) · Multiple-choice knapsack (MCKP) · Knapsack with setups (KPS)
-
3. Packing problems
Pack items of given weights into the minimum number of bins of capacity \(c\): bin packing and cutting stock.
-
4. Coloring problems
Color the vertices of a graph so that adjacent vertices get different colors, using the minimum number of colors: vertex coloring.
-
5. Clique problems
Find a largest set of pairwise adjacent vertices of a graph: maximum clique, maximum stable set and the weighted variants.
-
6. Routing problems
Find a shortest closed route that visits every city once: the travelling salesman problem, the metric and the asymmetric TSP.
Travelling salesman (TSP) · Metric and asymmetric TSP (ATSP)
-
7. Scheduling problems
Assign jobs to parallel machines so that the makespan is minimum: identical, uniform and unrelated machines.
-
8. Lot sizing problems
Plan the production of every period at minimum total cost: capacitated and uncapacitated lot sizing, and their variants.