## DM811 – Heuristics for Combinatorial Optimization## ScheduleFirst 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
## 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[A1] J.J. Bentley. Fast Algorithms for Geometric Traveling Salesman Problems. ORSA Journal on Computing, 1992, vol. 4, issue 4, pp. 387-411.
[A2] D. S. Johnson and L. A. McGeoch. The Traveling Salesman Problem: A Case Study in Local Optimization, Local Search in Combinatorial Optimization, E. H. L. Aarts and J. K. Lenstra (editors), John-Wiley and Sons, Ltd., 1997, pp. 215-310.
[A3] M. L. Fredman, D. S. Johnson, L. A. McGeoch and G. Ostheimer, Data Structures for Traveling Salesmen, J. Algorithms, 18:3 (1995), pp. 432-479.
[A4] Ravindra K. Ahuja, Özlem Ergun, James B. Orlin and Abraham 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
[A5] I.M. Whittley and G.D. Smith. The Attribute Based Hill Climber. Journal of Mathematical Modelling and Algorithms 3(2), 2004
[A6] T. Schiavinotto and T. Stützle. A review of metrics on permutations for search landscape analysis. Computers & Operations Research Volume 34, Issue 10, October 2007, Pages 3143-3153
[A7] Kernighan, B. & Lin, S. An Efficient Heuristic Procedure for Partitioning Graphs Bell System Technical Journal, 1970, 49, 291-307
[A8] Lin, S. & Kernighan, B. W. An Effective Heuristic Algorithm for the Traveling Salesman Problem Operations Research, 1973, 21, 498-516
## External Links## ExamProject assignment: Text (launched September 29, 2008, updated October 9, 2008)
Hand in deadline: Monday, October 27, 2008 Past exam projects: ## Re-ExamProject assignment: Text (launched December 14, 2008)
## Course Evaluation |