DM811 – Heuristics for Combinatorial Optimization

Schedule

First quarter 2008: Monday 10-12 Tuesday 8.15-10.00 in room U66 and Thursday 8.15-10.00 in IMADA Seminarrum starting August 25, 2008.

Lectures

0. 22.05.2008 Course Presentation [slides]
1. 25.08.2008 Introduction, Overview and Terminology [slides]
2. 28.08.2008 General Methods and Basic Algorithms [slides]
3. 01.09.2008 Complete, Incomplete, Greedy Search [slides]
4. 04.09.2008 Laboratory [Assignment] [Checker] [RanTim] [had] [ts.c]
5. 08.09.2008 Construction Heuristics and Enhancement of Greedy Search [slides]
6. 11.09.2008 Local Search (1) [slides]
7. 15.09.2008 Local Search (2) [slides]
8. 16.09.2008 Laboratory [Assignment]
9. 18.09.2008 Implementation Details, Incremental Updates [slides]
10. 23.09.2008 Laboratory [Assignment]
11. 25.09.2008 Very Large Scale Neighborhoods [slides]
12. 30.10.2008 Stochastic Local Search Methods [slides]
13. 02.10.2008 Experimental analysis [slides] [R notes (last updated October 2, 2008, 16:16)]
14. 07.10.2008 Optimizing Program Performance - Laboratory [slides]

Course Material

Books

  • [B1] Constraint-Based Local Search, P. Van Hentenryck and L. Michel. The MIT Press (2005).

  • [B2] Stochastic Local Search: Foundations and Applications, H. Hoos and T. Stützle, 2005, Morgan Kaufmann

  • [B3] Handbook of Approximation Algorithms and Metaheuristics. T.F. Gonzalez, Chapman & Hall/CRC Computer and Information Science, 2007.

  • [B4] Search methodologies: introductory tutorials in optimization and decision support techniques E.K. Burke, G. Kendall, 2005, Springer, New York

  • [B5] Introduction to algorithms. T.H. Cormen and C.E. Leiserson and R.L. Rivest, MIT press (2001).

  • [B6] Theoretical Aspects of Local Search. Michiels, W.; Aarts, E. & Korst, J. Springer Berlin Heidelberg, 2007

Scientific Articles

External Links

Exam

Project assignment:

Hand in deadline: Monday, October 27, 2008

Past exam projects:

Re-Exam

Project assignment:

  • Text (launched December 14, 2008)

Course Evaluation

Students’ Evaluation.