DM811 – Heuristics for Combinatorial Optimization

Schedule

Topics

Course Material

Main References:

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

• [B2] S. Russell and P. Norvig. Artificial Intelligence: A Modern Approach. (Part II). Third Edition. Prentice Hall, 2003.

• [B3] Comet Tutorial (see doc in Comet Application)

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

• [B5] H. Hoos and T. Stuetzle, Stochastic Local Search: Foundations and Applications, 2005, Morgan Kaufmann

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

• [A1] J. Condell, J. Wade, L. Galway, M. McBride, P. Gormley, J. Brennan and T. Somasundram. Problem solving techniques in cognitive science. Artificial Intelligence Review, Springer Netherlands, 2010, 34, 221-234

• [A2] J.J. Bentley. Fast Algorithms for Geometric Traveling Salesman Problems. ORSA Journal on Computing, 1992, vol. 4, issue 4, pp. 387-411.

• [A3] D.P. Bertsekas, J.N. Tsitsiklis and C. Wu. Rollout Algorithms for Combinatorial Optimization. Journal of Heuristics, 1997, 3(3), 245-262

• [A4] T. Schiavinotto and T. Stuetzle. A review of metrics on permutations for search landscape analysis. Computers & Operations Research, 2007, 34(10), 3143-3153

• [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

• [A6] P. Hansen and N. Mladenovic Variable Neighborhood Search: Principles and Applications (2001) European Journal of Operational Research, 130(3), 449–467.

• [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

• [A8] R.K. Ahuja, O. Ergun, J.B. Orlin and A.P. Punnen. A survey of very large-scale neighborhood search techniques Discrete Applied Mathematics, Volume 123, Issues 1-3, 15 November 2002, Pages 75-102

• [A9] Kernighan, B. & Lin, S. An Efficient Heuristic Procedure for Partitioning Graphs Bell System Technical Journal, 1970, 49, 291-307

• [A10] Lin, S. & Kernighan, B. W. An Effective Heuristic Algorithm for the Traveling Salesman Problem Operations Research, 1973, 21, 498-516

Links and Software

• [L1] Comet (see also Resources)

• [L2] George Polya How to Solve It (1945)

• [L3] Evolutionary Algorithms (Scholarpedia entry)

• [L4] Genetic Algorithms (Scholarpedia entry)

• [L5] M. Chiarandini. R notes. previous edition.

• [L6] Boxplot

Exam

Project assignment:

• Text (published on December 22, 2010; last update on January 3, 2011)

• Instances

• List of questions

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

Past exam projects:

• Comment list (published 22.09.2009)

• Text (published 25.09.2009, updated ) Final results

• Fall 2008

  • answer model 1. Comments.

  • answer model 2. Comments.

  • answer model 3. Comments.

• Fall 2007

• Fall 2006

• Fall 2005