DM811 – Heuristics for Combinatorial Optimization

Schedule

Autumn 2009, first quarter:
Tuesday 8.15-10.00 in IMADA Seminarrum
Wednesday 10.15-12.00 in IMADA Seminarrum
First lecture: August 25, 2009.

Topics

Lec. Date Topic Slides Literature and Assignments
0. 04.05.2009 Course Presentation 2x2.pdf
1.25.08.2009 Combinatorial Optimization, Problem Solving and Heuristics 2x2.pdf [B2, chp. 1] [B4, chp. 2] [assignment n. 1]
2.26.08.2009 Generalities: Construction Heuristics, Local Search and Metaheuristics + Basic Concepts in Algorithmics 2x2.pdf [A1]
3.01.09.2009 Basic Concepts in Algorithmics 2x2.pdf [B6, chp. 34]
4.02.09.2009 Assignment discussion + Experimental Analysis 2x2.pdf [N1] [assignment n. 2]
5.08.09.2009 Experimental Analysis + Construction Heuristics 2x2.pdf [B9, sec. 4.1, 4.2, chp. 5]
6.09.09.2009 Construction Heuristics + Metaheuristics see lec. 5 [L5] [A7] [B2, pp. 455, 492, 92, 89]
7.15.09.2009 Construction Heuristics for TSP see lec. 5 [A2] [L7] [2x2.pdf] [assignment n. 3]
8.16.09.2009 Local Search: Components, Basic Algorithms, Complexity 2x2.pdf [B1, chp. 1,2,6]
9.22.09.2009 Local Search: Neighborhoods and Landscape Analysis see lec. 8 [B1, chp. 3,4][B2, chp. 5] [A8] [2x2.pdf]
10.23.09.2009 Efficient Local Search: Incremental Updates and Neighborhood Pruning 2x2.pdf [A2] [B2, sec. 9.2] [L8]
11.29.09.2009 Efficient Local Search. Stochastic Local Search & Metaheuristics 2x2.pdf [B1, chp. 7] [B2] [A9] [A3]
12.30.09.2009 Stochastic Local Search & Metaheuristics see lec.11 [assignment n. 4]
13.06.10.2009 Very Large Scale Neighborhoods 2x2.pdf [A4] [B1, pp. 29-32] [A5]
14.07.10.2009 Configuration Tools and Software Demo 2x2.pdf [N1, chp. 3] [L9] [material on Comet] [coloring script] [Content Map]

Course Material

Books

Main book:

References and Further Reading:

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

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

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

  • [B5] P.V. Hentenryck and L. Michel. Constraint-Based Local Search. The MIT Press, Cambridge, USA, 2005.

  • [B6] T. Cormen, C. Leiserson, R. Rivest and Stein. Introduction to algorithms. MIT press, 2001.

  • [B7] M.R. Garey and D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco, CA, USA, 1979

  • [B8] J. Bondy and U. Murty. Graph Theory. Springer London, 2008.

  • [B9] S. Russell and P. Norvig. Artificial Intelligence: A Modern Approach. Prentice Hall, 2003.

Scientific Articles

  • [A9] H.H. Hoos and E. Tsang. Local Search Methods. Chapter 5, F. Rossi, P.V. Beek and T. Walsh (ed.). Handbook of Constraint Programming, Elsevier, 2006

Lecture Notes

External Links

Assignments

Resources

Exam

Project:

  • Text (published 25.09.2009, updated )

  • Instances Instances.tgz (published 25.09.2009)

  • Extended set of instances for race testing [24 Type E] [21 Type U] (published 13.10.2009, updated 21.10.2009)

  • Instance reader in C and in Java (published 25.09.2009)

  • Solution checker: fctt-checker (published 25.09.2009, updated 28.09.2009, updated 07.10.2009)

  • Comment list (published 22.09.2009)

  • FAQs

Hand in deadline: end of October 2009

Reexam

Project:

Hand in deadline: April 19, 2010

Past exam projects:

Course Evaluation