Exercises¶
Exercises with worked solutions, chapter by chapter, with the same parts and groups as the menu. Try each exercise on your own first: the solution opens with a click.
Combinatorial optimization¶
- 1. Combinatorial optimization problems · 8 exercises
Selected problems¶
- 2. Knapsack problems · 6 exercises
- 3. Packing problems · 6 exercises
- 4. Coloring problems · 5 exercises
- 5. Clique problems · 5 exercises
- 6. Routing problems · 7 exercises
- 7. Scheduling problems · 5 exercises
- 8. Lot sizing problems · 5 exercises
Formulations¶
- 9. Formulations of knapsack problems · 12 exercises
- 10. Formulations of packing problems · 6 exercises
- 11. Formulations of coloring problems · 5 exercises
- 12. Formulations of clique problems · 8 exercises
- 13. Formulations of routing problems · 6 exercises
- 14. Formulations of scheduling problems · 5 exercises
- 15. Formulations of lot sizing problems · 9 exercises
Dynamic programming¶
- 16. Principles of dynamic programming · 5 exercises
Knapsack problems¶
- 17. DP for the 0/1 knapsack problem · 5 exercises
- 18. DP for the unbounded knapsack problem · 5 exercises
- 19. DP for the bounded knapsack problem · 5 exercises
- 20. DP for the subset sum problem · 5 exercises
- 21. DP for the multiple-choice knapsack problem · 5 exercises
- 22. DP for the multidimensional knapsack problem · 5 exercises
- 23. DP for the knapsack problem with setups · 5 exercises
- 24. DP for the multiple knapsack problem · 5 exercises
Lot sizing problems¶
- 25. DP for the uncapacitated lot sizing problem · 3 exercises
- 26. DP for the capacitated lot sizing problem · 2 exercises
Miscellaneous problems¶
- 27. DP for the coin change problem · 5 exercises
- 28. DP for the rod cutting problem · 5 exercises
Heuristics¶
- 29. Heuristic algorithms: definitions · 5 exercises
- 30. Constructive heuristics · 15 exercises
- 31. Local search · 12 exercises
- 32. Metaheuristics · 17 exercises
- 33. MIP heuristics for the classical problems · 5 exercises
Approximation¶
- 34. Principles of approximation algorithms · 5 exercises
Knapsack problems¶
- 35. Approximation algorithms for the knapsack problem · 15 exercises
Packing problems¶
- 36. Approximation algorithms for bin packing · 12 exercises
Coloring problems¶
- 37. Vertex coloring: limits of approximation · 5 exercises
Clique problems¶
- 38. Maximum clique: limits of approximation · 4 exercises
Routing problems¶
- 39. The TSP: the general case and the metric case · 3 exercises
Scheduling problems¶
- 40. Approximation for P||Cmax · 3 exercises
Ad hoc algorithms¶
Knapsack problems¶
- 41. Knapsack: branch-and-bound on the critical item · 4 exercises
Coloring problems¶
- 42. Vertex coloring: the DSATUR branch-and-bound · 5 exercises