DM811 – Heuristics for Combinatorial Optimization

Marco Chiarandini (marco@imada.sdu.dk)

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

[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

Exam

Project assignment:

Text (launched September 29, 2008, updated October 9, 2008)
Instances [11MB]
Solution Validator

Hand in deadline: Monday, October 27, 2008

Past exam projects:

Re-Exam

Project assignment:

Text (launched December 14, 2008)

Course Evaluation

Students’ Evaluation.