DM841 - Heuristics and Constraint Programming for Discrete Optimization

Schedule

The course runs in Fall 2015, in weeks 36-52, from 31st of August to 17th of December

Introductory Classes

Constraint Programming Part

	Date	Topic and Slides	Literature and Assignments
0	26.05	Presentation
1	31.08	Course introduction, Motivations, Discrete Optimization
2	02.09	Modeling and Solving CSPs - Overview	[L3]
3	03.09	Introduction to Gecode	[MPG, Ch 1,2,3,4]
4	07.09	More on Gecode and examples
5	09.09	Yet more examples - Solving CSP, Overview	[MPG, Ch 10] [V3]
6	10.09	Examples on consistency levels and global constraints	[ C++ Video ]
7	14.09	Modeling: Global constraints	[HK sc. 7.1-7.2] [MPG, ch 13] [V1 ch 2-4]
8	16.09	Modeling: Global constraints
9	17.09	Class exercises modelling	[S] [ Exercise ] [ code ] [ solution ] [V4]
10	21.09	Class exercises modelling	[BK ch 1]
11	23.09	Elements of C++	[L2] [ Obligatory Assignment 1 ] [ sol, script ]
12	24.09	Notions of local consistency	[B]
13	28.09	Constraint Propagation Algorithms for AC	[B] [Ba]
14	30.09	Further notions of local consistency	[B] [SC]
15	01.10	Exercises
16	05.10	Propagation Events and Gecode Implementation, Exercises	[B] [SC] [MPG ch. 22,23,24,25,26]
17	07.10	Implementation issues for ObAss-1-1
18	08.10	Propagation Events and Gecode Implementation, Exercises	[B] [SC] [MPG ch. 22] [ Obligatory Assignment 2 ] [ sol]
		Autumn break
19	19.10	Filtering algorithms for global constraints	[HK] [V1, ch 8]
20	21.10	More Filtering Algorithms
21	22.10	More Filtering Algorithms - filtering algorithms for scheduling	[Hoo sc 3.13, 3.14]
22	26.10	Search	[Be, ch 4] [SC] [MPG, ch 8,9] [V1, ch 9-10]
23	28.10	Set Variables	[MPG, ch 5, 6] [V1, ch 6,7] [ Midterm Assignment ]
24	29.10	Symmetry breaking	[GPP] [V1, ch 5] [ Reexam ]

Local Search Part

	Date	Topic and Slides	Literature and Assignments
1	09.11	Satisfiability.	[L5]
2	11.11	Local Search Introduction	[HM, ch 1,2 (in BB)]
3	12.11	Local Search Algorithms	[MAK ch 1,2,4]
4	16.11	Theory of Local Search	[MAK ch 1,2,4]
5	18.11	Theory of Local Search	[SS]
6	19.11	Software Installation	Installation, Resources
7	23.11	Solvers. Practice	[HT (in BB)]
8	25.11	Instructions	[ Obligatory Assignment 1 ]
9	26.11	Training
10	30.11	Training. Working Environment
11	02.12	Exercises (SMTWTP, Steiner, p-median). Efficiency issues	[MAK, ch 3]
12	03.12	Efficiency issues (TSP)	[Ben]
13	07.12	Stochastic Local Search and Metaheuristics	[HM] [ Obligatory Assignment 2 ] [ feedback.txt ]
14	10.12	Experimental analysis
15	14.12	Experimental analysis	[L6] [L9]
16	16.12	Experimental analysis & Evolutionary algorithms	[R (in BB)] [L7, L9, L10]
17	17.12	Construction heuristics for TSP and CVRP & LS & Metaheuristics & ACO	[BT] [L9] [ Final Assignment ] [ FAQ ]
		Very Large-Scale Neighborhood Search	[AROP] [LK]
		Algorithm selection	[BSPV] [L12]

Course Material

Literature

No textbook is required. The following books are recommended.

Main books:

[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.

Other references

Books

[BK] Brucker, P. & Knust, S. Complex Scheduling. Springer Berlin Heidelberg, 2012
[Hoo] J.N. Hooker, Integrated Methods for Optimization. Springer, 2007
[MAK] W. Michiels, E. Aarts and J. Korst. Theoretical Aspects of Local Search. Springer Berlin Heidelberg, 2007

Chapters and articles:

[HK] W.J. van Hoeve and I. Katriel. Global Constraints. Chap. 7 in [RBW].
[B] C. Bessiere. Constraint propagation. Chap. 3 in [RBW]. Also as Technical Report LIRMM 06020, March 2006
[S] B. Smith. Modeling. Chap. 11 in [RBW]

[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

[Be] Peter van Beek, Backtracking Search Algorithms, pp 85-134 in [RBW]
[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]

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

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

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

[R] 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)

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

[BSPV] 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.

[AEOP] 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

[LK] Lin, S. & Kernighan, B. W. [http://www.jstor.org/stable/169020 /An Effective Heuristic Algorithm for the Traveling Salesman Problem/] Operations Research, 1973, 21, 498-516

Videos

[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

Software

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.

Date: 2016-01-04T19:36+0100

Author: marco

Org version 7.9.3f with Emacs version 24

Validate XHTML 1.0