Lectures
Note: during the course, this page is frequently updated, make sure that you
reload your page!
| Lec. | Date | Topic and slides | Literature and Assignments |
|---|
| 0 | 03.05 | Presentation | |
| 1 | 29.08 | Combinatorial Optimization, Methods and Models (2x2). Review (2x2). | [B6 ch.2] [B2 ch.4,5] [ Assignment 1] |
| 2 | 30.08 | Construction Heuristics, Local Search, Solver Systems (2x2) | [B7 sc.1.4] |
| 3 | 02.09 | Solver System and Working Environment (2x2) | [B3 ch.1-4,9,18] |
| 4 | 05.09 | Construction Heuristics (2x2) + Assignment discussion & analysis (scripts) | [L2, S3, S4] [A1] [B5 p.455] [ Exercises 1] [ Assignment 2] |
| 5 | 12.09 | Construction Heuristics, TSP (2x2) | [A2 sc.1-4] [V2, V3] |
| 6 | 15.09 | The SAT problem (2x2) | [V1] |
| 7 | 16.09 | Local Search: Components, Basic Algorithms (2x2) | [B5 sc.1.5] [B1 ch.1,2,6] [ Exercises 2] |
| 8 | 19.09 | Local Search: Components and Examples: SAT, TSP, MaxIndSet (2x2) | [ Assignment 3] |
| 9 | 22.09 | Local Search: Neighborhoods and Search Landscape (2x2) | [B1 ch.3,4] [B5 ch.5] [A3] [V4] |
| 10 | 23.09 | Efficient Local Search: Incremental Updates and Neighborhood Pruning (2x2) | |
| 11 | 26.09 | Examples (2x2) | [ Exercises 3] |
| 12 | 29.09 | Stochastic Local Search & Metaheuristics (2x2) | [B1 ch.7] [A4, A5] |
| 13 | 30.09 | Examples (2x2) | [ Assignment 4 ] |
| 14 | 03.10 | Stochastic Local Search & Metaheuristics (2x2) | [A6] |
| 15 | 06.10 | Methods for the Analysis of Experimental Results (2x2) | [L2 ch.1,2,3] [A7] |
| 16 | 10.10 | Exercises | |
| 17 | 13.10 | Exercises | [ R script ] [ Final Project launched ] |
| 18 | 14.10 | Very Large Scale Neighborhoods (2x2) | [A8] [ Guidelines ] |
Resources
Literature
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
Animations, Visualizations, Games
Evaluation
-
Obligatory assignments, pass/fail, evaluation by the teacher.
-
Final project (October 13 - November 5), Danish 7-scale with external censorship.
Author: Marco Chiarandini
Date: 2011-10-20 11:36:05 CEST
HTML generated by org-mode 6.36c in emacs 23
|