DM811 – Heuristics for Combinatorial Optimization

Marco Chiarandini (marco@imada.sdu.dk)

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:

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

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

[A1] A. Newell and H.A. Simon. Computer science as empirical inquiry: symbols and search. Communications of the ACM, ACM, 1976, 19(3), 113-126

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

[A3] M.L. Fredman, D.S. Johnson, L.A. Mcgeoch and G. Ostheimer. Data Structures for Traveling Salesmen. Journal of Algorithms, 1995, 18(3), 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] Kernighan, B. & Lin, S. An Efficient Heuristic Procedure for Partitioning Graphs Bell System Technical Journal, 1970, 49, 291-307

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

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

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

[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

[N1] Experimental Analysis of Optimization Heuristics Using R

External Links

[L1] A compendium of NP optimization problems
[L2] Complexity zoo
[L3] Travelling Salesman Problem
[L4] R free software environment for statistical computing and graphics
[L5] Search Techniques (from Cosytec)
[L6] Graph coloring instances
[L7] CGAL A free Computational Geometry Algorithms Library. (It includes the k-d trees data structure.)
[L8] T. Stützle’s implementation of local search for the traveling salesman problem
[L9] Comet

Assignments

Assignment Sheet n. 1 (posted 21.08.2009)
Assignment Sheet n. 2 (posted 02.09.2009)
Assignment Sheet n. 3 (posted 17.09.2009)
Assignment Sheet n. 4 (posted 30.09.2009)

Resources

Random generator and time counter RanTim.tgz.
A program to check solutions to instances of the graph coloring problem. Refer to the assignment sheet n.1 for details on the format.
Page on Queen Graphs
Instances for Assignment n. 2

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

Final results

Hand in deadline: end of October 2009

Reexam

Project:

Text (published 21.03.2010)
Instances pphp-instances.tgz (86MB) (published 21.03.2010)

Hand in deadline: April 19, 2010

Past exam projects:

Fall 2008
- answer model 1. Comments.
- answer model 2. Comments.
- answer model 3. Comments.
Fall 2007
Fall 2006
Fall 2005

Course Evaluation