Schedule
... see timetable
You can import the schedule in your calendar using the iCalendar file at
this URL
Introductory Classes
Local Search Part
| Date | Topic and Slides | Literature and Assignments |
|---|
| 0 | 26.05 | Presentation | |
| 1 | 01.09 | Course introduction, Motivations, Combinatorial Optimization, Methods | [MAK, appA,B] [ Review ] |
| 2 | 02.09 | Solution methods. SAT | [HM, ch 1,2] [L1; RN] [V1] |
| 3 | 05.09 | Local Search and Metaheuristics | [HM, ch 2] |
| 4 | 08.09 | C++ Review | [S] [L4] [ Code ] |
| 5 | 09.09 | Local Search in EasyLocal++ | [DS] |
| T1 | 10.09 | Bus Driver Example | [ Code ] |
| T2 | 15.09 | Practice | |
| 6 | 18.09 | Local Search: Iterative Improvement and Runners | [HM, ch 2; HS ch 2] |
| T3 | 19.09 | Practice | |
| 7 | 23.09 | Stochastic Local Search and Metaheuristics | [HM, ch 2; HS ch 2] |
| 8 | 25.09 | Simulated Annealing | [RBW ch5] [MAK ch 7] |
| 9 | 26.09 | Tabu Search (see lec 8). Working Environment | [MAK ch 7] |
| 10 | 29.09 | Variable Neighborhood Search (see lec 8). Experimental analysis | [HaMl] [ ObAss1 ] |
| 11 | 01.10 | Experimental analysis (see lec 10) | |
| T4 | 03.10 | Q&A. Efficiency issues in SAT | [ ObAss2 ] |
| 12 | 07.10 | SMTWT. Efficiency issues. Neighborhoods and Landscapes | |
| 13 | 22.10 | Examples: Binary Programming, TSP, Steiner Tree, Parallel Machines, Graph Coloring | [ ObAss3 ] |
| 14 | 24.10 | Evolutionary Algorithms. Midway Evaluation | |
Constraint Programming Part
| Date | Topic and Slides | Literature and Assignments |
|---|
| 1 | 29.10 | Introduction to Constraint Programming | [L5] |
| 2 | 31.10 | Example and Installation issues in Gecode | [ Gecode ] [MPG, Ch 1,2,3] |
| 3 | 05.11 | Solving CSPs - Overview | |
| 4 | 07.11 | Introduction to Gecode | |
| 5 | 12.11 | Global Constraints | [MPG, ch 4; HK sc. 7.1-7.2] [R sc. 1-2] |
| T1 | 14.11 | Global Constraints and Modeling exercises | [VH ch 2-4] [ ObAss1 ] |
| T2 | 19.11 | More on Global Constraints and Examples | [MPG, ch 4, 7.4] [MPG ch 16] [LC] |
| 6 | 21.11 | Notions of local consistency | [B] [ Rosetta ] [MPG ch 18, Video ] [ C++ Video ] [CHOP] |
| 7 | 25.11 | Constraint propagation algorithms for AC | [B] [Ba] |
| 8 | 28.11 | Exercises. Constraint Propagation Algorithms for AC | [B] [Ba] |
| 9 | 02.12 | Further notions of local consistency | [B] [SC] |
| 10 | 03.12 | Propagation Events and Gecode Implementation | [B] [SC] [MPG ch. 22,23,24,25,26] |
| 11 | 05.12 | Filtering algorithms for global constraints | [HK], [VH, ch 8] |
| T3 | 08.12 | Exercises | [ ObAss2 ] |
| T4 | 09.12 | More Filtering Algorithms (slides lec 11) | [HK] |
| 12 | 12.12 | Search | [RBW, ch 4 (in BB)] [SC] [MPG, ch 8,9] [VH, ch 9-10] |
| 13 | 16.12 | Set Variables | [MPG, ch 5, 6] [VH, ch 6,7] |
| 14 | 17.12 | Symmetry breaking | [GPP] [VH, ch 5] |
| T4 | 19.12 | Finishing previous lectures + ObAss2 | [ ObAss3 ] |
Course Material
Literature
No textbook is required. The following books are recommended.
Main books:
- [HM] P.V. Hentenryck and L. Michel. Constraint-Based Local Search. The MIT Press, Cambridge, USA, 2005.
- [RBW] F. Rossi, P. van Beek and T. Walsh (ed.), Handbook of Constraint Programming, Elsevier, 2006
- [MPG] C. Schulte, G. Tack, M.Z. Lagerkvist, Modelling and Programming with Gecode 2013
Other references
Books
- [MAK] W. Michiels, E. Aarts and J. Korst. Theoretical Aspects of Local Search. Springer Berlin Heidelberg, 2007
- [HS] H. Hoos and T. Stuetzle, Stochastic Local Search: Foundations and Applications, 2005, Morgan Kaufmann
- [BBHMW] A. Biere, A. Biere, M. Heule, H. van Maaren and T. Walsh. Handbook of Satisfiability Volume 185 Frontiers in Artificial Intelligence and
Applications. IOS Press, 2009
- [RN] S. Russell and P. Norvig. Artificial Intelligence: A Modern Approach. (Part II, chp. 3,4,6). Third Edition. Prentice Hall, 2010.
- [S] B. Stroustrup. The C++ Programming Language, Fourth Edition, 2013
- [KR] Kernighan, D. Ritchie. The C Programming Language, Second Edition
1988 Englewood Cliffs, NJ: Prentice Hall
Chapters and articles:
- [KLR] D.E. Knuth, T. Larrabee and P.M. Roberts. Mathematical writing. Mathematical Association of America, 1989
- [DS] 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.)
- [HaMl] P. Hansen and N. Mladenovic Variable Neighborhood Search: Principles and Applications (2001) European Journal of Operational
Research, 130(3), 449–467.
- [HK] W.J. van Hoeve and I. Katriel. Global Constraints. Chap. 7 in [RBW].
- [R] J.-C. Regin. Global Constraints and Filtering Algorithms
J-C. Régin "Constraints and Integer Programming Combined", Kluwer,
M. Milano editor, 2003
- [B] C. Bessiere. Constraint propagation. Chap. 3 in [RBW]. Also as
Technical Report LIRMM 06020, March 2006
- [LP] M.Z. Lagerkvist and G. Pesant. Modeling Irregular Shape Placement Problems with Regular Constraints. First Workshop on Bin Packing and
Placement Constraints BPPC'08, 2008
- [SC] C. Schulte and M. Carlsson. Finite domain constraint programming systems. Chap. 14 in [RBW]
- [CHOP] H. Cambazard, E. Hebrard, B. O'Sullivan and
A. Papadopoulos. Local search and constraint programming for the post enrolment-based course timetabling problem. Annals of Operations Research, Springer
Netherlands, 2010, 1-25
- [Ba] R. Barták. Theory and Practice of Constraint Propagation. Proceedings of CPDC2001 Workshop, 2001, 7-14
- [VH] Pascal Van Hentenryck. Discrete Optimization. Coursera. 2013. Local Directory
- [GPP] I.P. Gent, K.E. Petrie and J.-F. Puget. Symmetry in Constraint Programming, pp 329-376 in [RBW]
Animations, Visualizations, Games
Evaluation
- Ordinary exam: During the course there will be mandatory
assignments. The final grade will be given by a weighted average of
the grades received in the assignments.
- Re-exam: it consists of a single project corresponding in size to the
multiple assignments during the course.
Examples of past LS projects:
Course Evaluation by Students
Date: 2015-01-30T16:09+0100
Author: marco
Org version 7.9.3f with Emacs version 24
Validate XHTML 1.0
|