DM841 - Heuristics and Constraint Programming for Discrete Optimization

Schedule

The course runs in Fall 2016, in weeks 36-52, from 5th of September to 22nd of December.

	Date	Topic and Slides	Literature and Assignments
0	26.05	Presentation
1	05.09	Course introduction, Motivations, Discrete Optimization
2	07.09	Constraint Programming Overview	[L3] Review
3	09.09	Introduction to Gecode	[MPG Ch 1,2,3,4] [L6]
4	12.09	Introduction to Gecode	[MPG Ch 1,2,3,4] [L6]
5	14.09	More on Gecode	[L2]
6	15.09	Elements of C++	[ C++ Video ] [L2] [L7] [Exercise]
7	19.09	Modelling in CP by examples	[RBW chp 11 (ref [S])] [V4, V5]
8	21.09	CSP model
9	22.09	Modeling: Global constraints	[HK sc. 7.1-7.2] [MPG, ch 13] [V1, ch 2-4] [V3]
10	26.09	Modeling: Global constraints	[HK sc. 7.1-7.2] [Obligatory Assignment 1]
11	29.09	Class exercises	[Exercise] [ solution ] [ code ]
12	03.10	Global constraints in Scheduling	[MPG sc 4.4.18]
13	05.10	Class exercises	[MPG ch 16, 21]
14	06.10	Notions of local consistency	[B]
15	10.10	Constraint Propagation Algorithms for AC	[B] [Ba] [Exercises] [sol]
16	12.10	Propagation Algorithms for AC	[B] [Sc] (see slides lec 15)
17	13.10	Further Notions of Local Consistency	[B]
		Autumn break	[Obligatory Assignment 2]
18	24.10	Rules Iteration, [Exercises: Set 1 / sol; Set 2 / sol]	[B] [SC] [MPG ch. 22,23,24,25,26]
19	26.10	Filtering Algorithms for Global Constraints	[HK]
20	27.10	More on Filtering Algorithms
21	31.10	Search	[Be, ch 4]
22	01.11	Random Restarts, Set Variables,	[MPG, ch 5, 6]
23	03.11	Symmetry breaking	[GPP] [Obligatory Assignment 3] [FAQ]
		Break

	Date	Topic and Slides	Literature and Assignments
1	14.11	Satisfiability, Local Search Introduction	[L5] [HM, ch 1,2 (in BB)]
2	16.11	Local Search Algorithms	[HS, sc 1.5 (in BB)] [HT (in BB)]
3	17.11	Theory of Local Search	[MAK ch 1,2,4]
4	21.11	Theory of Local Search
5	24.11	Stochastic Local Search and Metaheuristics	[HT (in BB)]
6	28.11	Solvers. EasyLocal	[S4] [BMFP, S5]
7	30.11	Guided example	[Obbligatory Assignment 4] [FAQ]
8	02.12	Training. Working Environment	[Exercises 1.1]
9	05.12	Training	[Exercises 1.2-1.10]
10	08.12	Efficiency issues, Efficiency issues (TSP)	[MAK, ch 3] [Ben]
11	12.12	Experimental analysis: descriptive statistics
12	14.12	Experimental analysis: inferential statistics, algorithm selection	[LDC]
13	15.12	Evolutionary algorithms & ACO	[R (in BB)] [L9, L10]
14	19.12	Very Large-Scale Neighborhood Search	[AROP in BB] [Final Assignment] [FAQ]

No textbook is required. The following books are recommended.

[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 2015
[Apt] Apt, K. R. Principles of Constraint Programming Cambridge University Press, 2003
[HM] P.V. Hentenryck and L. Michel. Constraint-Based Local Search. The MIT Press, Cambridge, USA, 2005.

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

Chapters and articles:

[B] C. Bessiere. Constraint propagation. Chap. 3 in [RBW]. Also as Technical Report LIRMM 06020, March 2006

[SC] C. Schulte and M. Carlsson. Finite domain constraint programming systems. Chap. 14 in [RBW]

[Ba] R. Barták. Theory and Practice of Constraint Propagation. Proceedings of CPDC2001 Workshop, 2001, 7-14

[GPP] I.P. Gent, K.E. Petrie and J.-F. Puget. Symmetry in Constraint Programming, pp 329-376 in [RBW]

[HT] H. Hoos and E. Tsang. Local search methods, chp 5 in [RBW]
[BMFP] Gustav Björdal, Jean-Noël Monette, Pierre Flener, Justin Pearson. A constraint-based local search backend for MiniZinc. July 2015, Volume 20, Issue 3, pp 325–345
[O] OscaR architecture

[LDC] Manuel López-Ibáñez, Jérémie Dubois-Lacoste, Leslie Pérez Cáceres, Mauro Birattari, Thomas Stützle, The irace package: Iterated racing for automatic algorithm configuration, Operations Research Perspectives, Volume 3, 2016, Pages 43–58

[V1] Pascal Van Hentenryck. Discrete Optimization. Coursera. 2013. Local Directory
[V2] C++ in one hour
[V3] Numberphile: Magic Square
[V4] Numberphile: The Queens problem
[V5] Numberphile: The Knights problem

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.

Reexam

Author: Marco Chiarandini

Created: 2017-02-20 Mon 16:05