DM877 - Constraint Programming

General information

Week	Date	Topic and Slides	Recommended Reading	Additional Reading
20	May 17	Course Presentation
36	Sep 1	Course Organization, Motivations, Discrete Optimization		Compendium
36	Sep 2	Constraint Programming by Example
36	Sep 3	Constraint Programming Languages and MiniZinc	[SMT] chp. 1	Puzzle Day
37	Sep 8	MiniZinc	[SMT] chp. 2	[GM] chp. 12 in BB
37	Sep 9	MiniZinc	[SMT] chp. 2
38	Sep 15	Global Constraints in MiniZinc	[SMT] chp. 2, sec 2.3; [HK] sc 7.1-7.2
38	Sep 16	Global Constraints in MiniZinc	[SMT] sc 2.3, [HK] sc 7.1-7.2	Assignment 1; Template
39	Sep 22	Constraint Satisfaction Model and Notions of Local Consistency	[S], [B], [BA]
39	Sep 23	Constraint Propagation Algorithms for AC	[B], [SC]
40	Sep 30	Further Notions of Local Consistency	[B]
40	Oct 1	Rule Iterations	[B], [SC]
41	Oct 5	Filtering Algorithms for Global Constraints	[HK], [Hoo ch 3]
41	Oct 8	Filtering Algorithms for Scheduling Constraints	[Hoo, sc. 3.13.1, 3.13.2; 3.14.1]	Assignment 2; Template
43	Oct 20	Search and Random Restarts	[Be, ch 4]
43	Oct 21	Set Variables
43	Oct 22	Symmetry Breaking	[GPP]	Final Assignment; Template

Week	Date	Notes and Assignments	Solutions
37	Sep 10	Sheet 1	solutions
38	Sep 17	Sheet 2	solutions
39	Sep 24	Sheet 3	solutions
40	Sep 29	Discussion
41	Oct 8	Sheet 4	solutions

No textbook is required. Excerpts from the following books will be used.

[RBW] F. Rossi, P. van Beek and T. Walsh (ed.), Handbook of Constraint Programming, Elsevier, 2006
[SMT] Peter J. Stuckey, Kim Marriott, Guido Tack. MiniZinc Handbook. 2020
[A] Apt, K. R. Principles of Constraint Programming Cambridge University Press, 2003
[GM] Maurizio Gabbrielli and Simone Martini. Programming Languages: Principles and Paradigms. Springer 2010.
[Hoo] J.N. Hooker, Integrated Methods for Optimization. Springer, 2007

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

Global Constraint Catalog by Nicolas Beldiceanu and Sophie Demassey. Full List and CP Systems.
CSPLib, a problem library for CP
Hakan’s page on solution scripts to 242 CP problems