DM826 - Modeling and Solving Constrained Optimization Problems

Schedule

... see timetable

You can import the schedule in your calendar using the iCalendar file at this URL

In bold the essential literature

	Date	Topic and Slides	Literature and Assignments
0	28.11.2013	Presentation
1	03.02	Constrained Optimization: an integrated approach (IP, CP, LS)	[RBW, ch 11 (in Bb)] [A2, A3]
2	05.02	Modelling in IP and CP, global constraints	[A1]
3	10.02	Global Constraints	[A4] [V1, lec. 2-4]
4	12.02	Introduction to Gecode	[STL, ch. 4] [STL ch. 2,3,,7]
5	17.02	Notions of local consistency	[A5]
6	19.02	Constraint propagation algorithms for AC	[A5] [ Obligatory Assignment 1 ]
7	03.03	Further notions of local consistency	[A5]
8	05.03	Constraint Propagation	[A6; *STL, ch. 22**,23,24,25,26]
9	10.03	Filtering algorithms for global constraints	[A4], [A8], [V1, lec. 8]
10	12.03	Search	[RBW, ch 4 (in BB)] [STL, ch 8,9] [V1, lec 9-10]
11	17.03	Search	[RBW, ch 4 (in BB)] [STL, ch 8,9] [V1, lec 9-10]
12	19.03	Set Variables	[STL, ch 5, 6] [V1, lec 6,7] [ Obligatory Assignment 2 ]
13	24.03	Symmetry breaking	[A9] [V1, lec 5]
14	26.03	Symmetry breaking	[ Obligatory Assignment 3 ]

In bold the essential literature

	Date	Material	Exercises
1	06.02	Modelling	[ preparation ]
2	13.02	Crosswords, Golomb ruler [STL ch 12], nurse scheduling, binpacking [STL, ch 19]	[ preparation ]
3	20.02	AC algorithms	[ preparation ]
4	06.03	Consistency levels and propagators	[ preparation ]
5	13.03	First assignment: matching under preferences [A8] [ code ] + filtering algorithms for scheduling [Hoo sc 3.13, 3.14]	[ preparation ]
6	20.03	Set variables	[ preparation ]
7	27.03	Cancelled

[RBW] F. Rossi, P. van Beek and T. Walsh (ed.), Handbook of Constraint Programming, Elsevier, 2006
[STL] C. Schulte, G. Tack, M.Z. Lagerkvist, Modelling and Programming with Gecode 2013

Books

[Hoo] J.N. Hooker, Integrated Methods for Optimization. Springer, 2007
[Apt] Apt, K. R. Principles of Constraint Programming Cambridge University Press, 2003
[MS] Marriott, K. & Stuckey, P. J. Programming with Constraints: An Introduction MIT Press, 1998
[HM] P. van Hentenryck and M. Milano. Hybrid Optimization, The Ten Years of CPAIOR. Springer, 2011, 45

Chapters and articles:

[A3] Linear Programming, chp. 29 in T. Cormen, C. Leiserson, R. Rivest and Stein. Introduction to algorithms. Third Edition. MIT press, 2009.

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

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

[A8] K. Iwama and S. Miyazaki. A Survey of the Stable Marriage Problem and Its Variants. International Conference on Informatics Education and Research for Knowledge-Circulating Society (ICKS), 2008
[A9] I.P. Gent, K.E. Petrie and J.-F. Puget. Symmetry in Constraint Programming, pp 329-376 in [RBW]

Videos

[V1] Pascal Van Hentenryck. Discrete Optimization. Coursera. 2013. Local Directory

Date: 2014-03-31T16:08+0200

Author: Marco Chiarandini

Org version 7.9.3f with Emacs version 24