DM811 – Heuristics for Combinatorial Optimization

Schedule

Autumn 2010, second quarter:
Monday 12.15-14.00 in IMADA Seminarrum
Wednesday 12.15-14.00 in IMADA Seminarrum
Friday 12.15-14.00 in U66
First lecture: November 8, 2010. Last lecture: December 22, 2010.

Topics

Lec. Date Topic Slides Literature and Assignments
0. 04.05.2010 Course Presentation 1x1.pdf
1. 08.11.2010 Combinatorial Optimization, Problem Solving and Heuristics 2x2.pdf 2x2.pdf [B5, chp. 1] [B7, chp. 2] [A1] [L2] [Assignment 1]
2.10.11.2010 Generalities: Construction Heuristics and Local Search + Intro to Comet 2x2.pdf [B2, chp. 3 and 6]
12.11.2010 Exercises in Comet
3.15.11.2010 Construction Heuristics + Metaheuristics (1/3) 2x2.pdf
4.17.11.2010 Construction Heuristics for TSP (2/3) 2x2.pdf [A2]
19.11.2010 Exercises in Comet
5.22.11.2010 Construction Heuristics + Metaheuristics (3/3) 2x2.pdf [A3] [B5, pp. 455, 492, 92, 89] [Assignment 2]
6.24.11.2010 Local Search: Components, Basic Algorithms, Complexity 2x2.pdf [B1, chp. 1,2,6]
26.11.2010 Exercises in Comet
7.29.11.2010 Local Search: Components and Examples 2x2.pdf [B1, chp. 1,2,6]
8.01.12.2010 Local Search: Neighborhoods and Search Landscape 2x2.pdf [A4] [Assignment 3] [steinertree]
03.12.2010 Exercises in Comet
9.06.12.2010 Stochastic Local Search & Metaheuristics (1/2) 2x2.pdf [B4, chp. 1,2,10-14] [chp. 7, B1] [A5 in BlackBoard]
10.08.12.2010 Stochastic Local Search & Metaheuristics (2/2) see lec. 9 [B1, chp. 7] [A6] [A7 in BlackBoard] [Assignment 4]
11.13.12.2010 Efficient Local Search: Incremental Updates and Neighborhood Pruning 2x2.pdf [Assignment 5]
12.15.12.2010 Very Large Scale Neighborhoods 2x2.pdf [A8,A9,A10] [Assignment 6] [check list]
17.12.2010 Exercises
13.20.12.2010 Methods for the Analysis of Experimental Results 2x2.pdf [L5] [L6]
14. 22.12.2010 Configuration Tools: F-race 2x2.pdf [N1] [Examples]

Course Material

Main References:

Further Reading:

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

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

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

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

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

  • [A7] C. Reeves. Genetic Algorithms. Chp. 3 In F. Glover and G. Kochenberger (eds.). Handbook of Metaheuristics, Kluwer Academic Publishers, Norwell, MA, USA, 2002, 57, 55-82

Links and Software

Exam

Project assignment:

Hand in deadline: at 15:00, January 25, 2011.

Past exam projects: