Formulations and their properties¶
Part 2 of the course, volume 2 of the lecture notes: chapters 9–15.
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.
Lecture notes (PDF) Exercises (PDF)
-
9. Formulations of knapsack problems
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)
-
10. Formulations of packing problems
Bin packing (BPP) · Cutting stock (CSP)
-
11. Formulations of coloring problems
Vertex coloring (VCP)
-
12. Formulations of clique problems
Maximum clique (MCP) · Weighted maximum clique
-
13. Formulations of routing problems
Travelling salesman (TSP) · Metric and asymmetric TSP (ATSP)
-
14. Formulations of scheduling problems
Identical parallel machines (P||Cmax)
-
15. Formulations of lot sizing problems
Capacitated lot sizing (CLS) · Lot sizing variants