Full index¶
How to use these notes¶
- Website and PDF. Each chapter of the website is a chapter of the lecture notes, with the same numbers and the same colors; long chapters are split into one page per section.
- At the top of each chapter a bar with the part, the PDF of the lecture notes, the slides, the exercises and the apps of the chapter; at the bottom, the link to the exercises.
- The problems. The definition of each problem is on its page of the course Combinatorial Optimization Problems: each chapter starts with the link.
The boxes have the same colors as in the lecture notes:
Definition
The precise meaning of a new concept.
Theorem, proposition, observation
A result to remember, with its hypotheses.
Example
A computation worked out in full, one step at a time.
Formula
In pink the formulas to keep at hand: the recurrences of dynamic programming.
Algorithm
The pseudo-code, step by step as in the lecture notes.
In green the key point to take away.
Proof: opens with a click
All proofs are included, but folded: first read the statement, then open the proof when you want to study it. The same holds for the solutions of the exercises.
All the pages of the website, in the order of the menu: the chapters with their sections and the other pages.
Principles¶
Knapsack problems¶
- 2. DP for the 0/1 knapsack problem · Exercises
- 3. DP for the unbounded knapsack problem · Exercises
- 4. DP for the bounded knapsack problem · Exercises
- 5. DP for the subset sum problem · Exercises
- 6. DP for the multiple-choice knapsack problem · Exercises
- 7. DP for the multidimensional knapsack problem · Exercises
- 8. DP for the knapsack problem with setups · Exercises
- 9. DP for the multiple knapsack problem · Exercises
Lot sizing problems¶
- 10. DP for the uncapacitated lot sizing problem · Exercises
- 11. DP for the capacitated lot sizing problem · Exercises