Unit 7: Discrete Optimization and Heuristics
April 28: Lecture 16 — Discrete Optimization
- Integer Programs
- Rounding
- Cutting Planes
- Branch and Bound
- Dynamic Programming
Resources:
- Slides
- Chapter 19 of [KW]
May 1: Exercises
May 5: Lecture 17 — Heuristics
- Constraint Programming
- Backtracking
- Construction Heuristics
- Local Search [MAK]
Resources:
- Slides
- Minizinc. Book, Global Constraints
- [MAK] W. Michiels, E. Aarts and J. Korst. Theoretical Aspects of Local Search. Springer Berlin Heidelberg, 2007. Chapters 1, 2, 3, 4, 7 go more in depth than we did in class.
May 8: Exercises
- Sheet 10. Solutions
- ROAR-NET API Specification
- ROAR-NET API Specification
- ROAR-NET API Specification Implementation
- ROAR-NET API Specification Implementation for TSP
- ROAR-NET API Specification Implementation for SMTWTP
May 12: Exercises
- Modeling in the ROAR-NET API specification [ROAR-NET API, MAK]
- Routing
Resources:
May 15: Exercises
- Modeling in the ROAR-NET API specification
- Scheduling
Resources:
May 19: Lecture 18 — Metaheuristics
- Metaheuristics [MAK, GP]
Resources:
- Slides
- [MAK] W. Michiels, E. Aarts and J. Korst. Theoretical Aspects of Local Search. Springer Berlin Heidelberg, 2007
- [GP] Michel Gendreau and Jean-Yves Potvin (eds) Handbook of Metaheuristics. 2019. International Series in Operations Research & Management Science book series (ISOR, volume 272). This reference is only for those interested in going in depth on each metaheuristic. There is one chapter per metaheuristic in the book. For the exam, the slides should be sufficient.