DM826 - Modeling and Solving Constrained Optimization Problems

This page will be frequently updated: reload your page!

Schedule


Spring 2012, third quarter, weeks 5-11	Monday, 16:00-18:00 in IMADA Seminarrum
First lecture: January 30, 2012	Wednesday, 12:00-14:00 in IMADA Seminarrum
Last lecture: March 16, 2012	Friday, 10:00-12:00 in IMADA Seminarrum


Lec.	Date	Topic and Slides	Literature and Assignments
0	05.12.2011	Presentation
1	30.01.2012	Modeling: an integrated approach (IP, CP, LS)	[A1] [ Python ]
2	01.02.2012	Overview on CP	[A1] [B1, ch 11 (in BB)]
3	03.02.2012	Overview on global constraints	[A2, sc 7.1-7.2] or [B2, chp. 5]
e1	06.02.2012	Exercises	[ Exercises ]
4	08.02.2012	Introduction to Gecode	[ B3, ch. 2,3,4]
5	10.02.2012	Notions of local consistency	[ A4 ]
e2	13.02.2012	Exercises (scripts)	[ Exercises ]
6	15.02.2012	Constraint propagation algorithms for AC	[ A4 ]
7	17.02.2012	Further notions of local consistency	[ A4, A5 ]
e3	20.02.2012	Exercises	[ Exercises ] [ Obligatory Assignment 1]
8	22.02.2012	Constraint Propagation	[ A3; A2, sc. 7.3.1; B3, ch. 21,22,23,24,25,26 ]
9	24.02.2012	Filtering algorithms for global constraints	[A2, sc. 7.3,7.4,7.5; A8]
e4	27.02.2012	Exercises (ex3-4, scheduling, scripts)	[ Exercises ] [B2 sc. 3.13, 3.14]
10	29.02.2012	Search	[B1, ch 4 (in BB); A3]
11	02.03.2012	Search	[B8, ch 2] [A3] [B3, ch. 7]
e5	05.03.2012	Exercises	[ Exercises ] [A9]
12	07.03.2012	Set variables (scripts)	[A2, sc 7.6; B3, ch 5] [ Obligatory Assignment 2 ]
e6	09.03.2012	Exercises
e7	12.03.2012	Exercises	[ Exercise ]
13	14.03.2012	Symmetries	[A6][A10]
14	16.03.2012	Logic-Based Benders Decomposition & Large Neighborhood Search	[B2, sc 2.3.6 or A7] [B1, ch 23; A11]
			[ Obligatory Assignment 3 (FAQ)]

[B1] F. Rossi, P. van Beek and T. Walsh (ed.), Handbook of Constraint Programming, Elsevier, 2006

[B2] J.N. Hooker, Integrated Methods for Optimization. Springer, 2007
[B3] C. Schulte, G. Tack, M.Z. Lagerkvist, Modelling and Programming with Gecode 2011
[B4] Apt, K. R. Principles of Constraint Programming Cambridge University Press, 2003
[B5] Marriott, K. & Stuckey, P. J. Programming with Constraints: An Introduction MIT Press, 1998
[B6] P. van Hentenryck and M. Milano. Hybrid Optimization, The Ten Years of CPAIOR. Springer, 2011, 45
[B7] Comet Manual.
[B8] M. Gagliolo. Online Dynamic Algorithm Portfolios PhD Thesis. 2010

Chapters and articles:

[A1] J.N. Hooker. Hybrid Modeling. pp 11-62 in [B6].
[A2] W.J. van Hoeve and I. Katriel. Global Constraints. Chap. 7 in [B1].
[A3] C. Schulte and M. Carlsson. Finite domain constraint programming systems. Chap. 14 in [B1]
[A4] C. Bessiere. Constraint propagation. Chap. 3 in [B1]. Also as Technical Report LIRMM 06020, March 2006
[A5] R. Bartak. Theory and Practice of Constraint Propagation. Proceedings of CPDC2001 Workshop, 2001, pp. 7-14.
[A6] I.P. Gent, K.E. Petrie and J.-F. Puget. Symmetry in Constraint Programming, pp 329-376 in [B1]
[A7] J. Hooker and G. Ottosson. Logic-based Benders decomposition. Mathematical Programming, Springer, 2003, 96 , 33-60
[A8] J.-C. Regin. Global Constraints: A Survey. pp 63-134 in [B6]
[A9] M.Z. Lagerkvist and G. Pesant. Modeling irregular shape placement problems with regular constraints. In First Workshop on Bin Packing and Placement Constraints BPPC'08, 2008.
[A10] P.J. Hawkins, V. Lagoon and P.J. Stuckey. Solving Set Constraint Satisfaction Problems using ROBDDs. 2005, 24 , 109-156

Three obligatory assignments, two during the course and one at the end, in weeks 12 and 13

Date: 2012-03-26 13:47:35 CEST

Author: Marco Chiarandini

Org version 7.6 with Emacs version 23