DM811 - Heuristics for Combinatorial Optimization

Table of Contents

Links
Schedule
Lectures
Resources
Assessment
Course Evaluation

Links

Schedule


Fall 2012, first quarter, weeks 35-41	Monday, 12:15-14:00
First lecture: September 3, 2012	Tuesday, 08:15-10:00
Last lecture: October 12, 2012	Thursday, 10:15-12:00

Lectures

Note: during the course, this page is frequently updated, make sure that you reload your page!


Lec.	Room	Date	Topic and slides	Literature and Assignments
1	U146	03.09	Combinatorial Optimization, Methods and Models. Review	[B1 appA,B; B6 ch4; B7 sc1.4; L1] [ Assignment 0, FAQ ]
2	U24A	04.09	Construction Heuristics and Local Search: an Overview	[B2 ch4,5]
3	Seminarrum	06.09	Assignment 0, discussion. Working Tools, Experimental Analysis	[L2, L3, S1-S8]
4	Seminarrum	10.09	Solver Systems, Construction Heuristics	[S1, B3, V2, V3, B2 ch.3,4, A1] [ Assignment 1, FAQ ]
5	U24A	11.09	Construction Heuristics TSP	[A2 sc.1-4, V2, V10]
6	Seminarrum	13.09	CH for TSP and the SAT problem	[A2 sc.1-4, V1]
7	Seminarrum	17.09	Exercises: SAT and GCP. Analysis Assignment 1. Local Search.	[B5 sc.1.5] [B1 ch.1,2,6] [ Assignment 2, FAQ ]
8	U24A	18.09	Local Search: Components, Basic Algorithms, Examples
9	Seminarrum	20.09	Examples
10	U71	24.09	Stochastic Local Search & Metaheuristics	[B1 ch.7] [A4, A5] [B5]
11	U24A	25.09	Local Search: Neighborhoods and Search Landscape	[B1 ch.3,4] [B5 ch.5] [A3] [V4]
12	Seminarrum	27.09	Efficient LS: Incremental Updates and Neighborhood Pruning	[B5 p. 271] [A2]
13	U146	01.10	Exercises: LS for GCP	[ coloring.co ] [ Assignment 3 ]
14	U24A	02.10	Stochastic Local Search & Metaheuristics: EA, ACO	[A6] [V11]
15	Seminarrum	04.10	Statistical Methods for Configuration and Tuning	[L2 ch.1,2,3] [A7]
16	U71	08.10	Exercises: SMTWP, TSP; Generalized LS Machines
17	U24A	09.10	Exercises: QAP, LOP	[ Final Project ] [ checker.cpp ] [ 16-8-2.sol ] [ FAQ ]
18	Seminarrum	11.10	Very Large Scale Neighborhoods	[A8]

Resources

Literature

Text book:

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

Further Reading:

Books:

[B2] S. Russell and P. Norvig. Artificial Intelligence: A Modern Approach. (Part II, chp. 3,4,6). Third Edition. Prentice Hall, 2010.
[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. (In BlackBoard)
[B5] H. Hoos and T. Stuetzle, Stochastic Local Search: Foundations and Applications, 2005, Morgan Kaufmann

[B6] E.K. Burke, G. Kendal, Search methodologies: introductory tutorials in optimization and decision support techniques 2005, Springer, New York
[B7] A. Schrijver. Theory of Linear and Integer Programming. Wiley Interscience, 1986.

Articles:

(Links work from within SDU network)

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

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

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

[A4] 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 (In BlackBoard)

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

[A6] 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 (In BlackBoard)

[A7] M. Birattari, T. Stuetzle, L. Paquete, K. Varrentrapp (2002). A racing algorithm for configuring metaheuristics. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2002), pp. 11-18, Morgan Kaufmann Publishers, New York.

[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

Links

[L1] George Polya How to Solve It (1945)

[L2] M. Chiarandini. R notes.
[L3] Boxplot

[L4] Evolutionary Algorithms (Scholarpedia entry)
[L5] Genetic Algorithms (Scholarpedia entry)
[L6] A compendium of NP optimization problems

Software

[S1] Comet (see also local information)
[S2] EasyLocal++ (L. Di Gaspero and A. Schaerf. Writing local search algorithms using EasyLocal++. In S. Voss and D.L. Woodruff, editors, Optimization Software Class Libraries, OR/CS. Kluwer Academic Publisher, Boston (MA), USA, 2002.)
[S3] LocalSolver
[S4] Google OR Tools

[S3] Manual for Unix shell utilities useful for parsing and other file managing
[S4] Local information on R
[S5] Timer for Java
[S6] API for parsing command line options in Java
[S7] Control and profiling of threads in Java
[S8] Gprof for C and C++: instructions

Animations, Visualizations, Games

[V1] The SAT Game
[V2] TSP nearest neighbor
[V3] Construction heuristics and 2-opt for TSP
[V4] Search Landscape Visualization
[V5] Tabu Search with 2-opt for Traveling Salesman
[V6] Tabu Search with Random Restart for QAP
[V7] Simulated Annealing on TSP
[V8] Annealing schedule simulation
[V9] Simulated Annealing and Ant Colony Optimization on TSP
[V10] Heuristics for TSP
[V11] Ant Colony path finding

Assessment

Obligatory assignments, pass/fail, evaluation by the teacher.
Final project (October 13 - November 3), Danish 7-scale with external censorship.

Final Project

[ Final Project ] [ checker.cpp ] [ 16-8-2.sol ] [ FAQ ]

Reexam

[ Text ] [ Instances ] [ Checker ]

Past final projects

Fall 2010
Fall 2009 (Final results), Reexam
Fall 2008
- answer model 1. Comments.
- answer model 2. Comments.
- answer model 3. Comments.
Fall 2007
Fall 2006
Fall 2005

Course Evaluation

Date: 2013-01-03 15:50:24 CET

Author: Marco Chiarandini

Org version 7.8.02 with Emacs version 23

Validate XHTML 1.0