DM826 - Modeling and Solving Constrained Optimization Problems

Schedule


Spring 2011, third quarter, weeks 5-11	Monday 10.15-12.00 in IMADA Seminarrum
First lecture: January 31, 2011.	Wednesday 10.15-12.00 in IMADA Seminarrum
Last lecture: March 18, 2011.	Friday 08.15-10.00 in IMADA Seminarrum


Lec.	Date	Topic	Literature and Assignments
0	29.11.2010	Presentation
L.1	31.01.2011	Introduction: an Integrated Approach, examples	[A1]
L.2	02.02.2011	Overview to modelling and CP	[A1; A2, sec. 7.1, 7.2]
E.1	04.02.2011	Intro, Comet and Gecode. n-Queens	[A3] [ exercises ]
L.3	07.02.2011	Examples of global constraints	[B1, chp. 5] [B2, chp. 11]
L.4	09.02.2011	Local consistency notions	[A4] [ exercises ]
E.2	11.02.2011		[ Obligatory Assignment 1 ]
L.5	14.02.2011	Local consistency notions	[A4; B4, chp. 5; B7, chp. 15] [ exercises ]
L.6	16.02.2011	Filtering algorithms for global constraints	[A2] [ exercises ]
E.3	18.02.2011
L.7	21.02.2011	Filtering algorithms for global constraints	[A2; A5; s. 3.8, B1] [ exercises ]
L.8	23.02.2011	Search	[B2, chp. 4,5]
E.4	25.02.2011
L.9	28.02.2011	Search and Symmetries	[A6]
L.10	02.03.2011	Symmetries	[ Obligatory Assignment 2 ]
E.5	04.03.2011	IP and CP fomulations of timetabling problems	[ BACP, B7, sec.9.6; Project team formation; IMADA Timetabling ]
L.11	07.03.2011	Set variables	[A2, sec. 7.6; B7, chp. 11; B3, chp. 5]
L.12	09.03.2011	Branch and price	[A7, B7, sec 22.3] [ exercises ]
E.6	11.03.2011
L.13	14.03.2011	Branch and price	[B8, chp. 9, sec. 2.1 ]
L.14	16.03.2011	Benders decompositions	[A8, B9, A9, B1, sec. 2.3.6, 2.3.7] [ Obligatory Assignment 3 ]

Books:

[B1] J.N. Hooker, Integrated Methods for Optimization. Springer, 2007
[B2] F. Rossi, P. van Beek and T. Walsh (ed.), Handbook of Constraint Programming, Elsevier, 2006
[B3] C. Schulte, G. Tack, M.Z. Lagerkvist, Modelling and Programming with Gecode 2010
[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] G. Desaulniers, J. Desrosiers and M.M. Solomon (ed.). Column Generation. Springer, 2005

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 [B2].
[A3] C. Schulte and M. Carlsson. Finite domain constraint programming systems. Chap. 14 in [B2]
[A4] C. Bessiere. Constraint propagation. Chap. 3 in [B2]. Also as Technical Report LIRMM 06020, March 2006
[A5] J.-C. Régin. Global Constraints: A Survey. pp 63-134 in [B6]
[A6] I.P. Gent, K.E. Petrie and J.-F. Puget. Symmetry in Constraint Programming, pp 329-376 in [B2]
[A7] M. Lübbecke and J. Desrosiers. Selected Topics in Column Generation. Oper. Res., 2005, 53(6) , 1007-1023
[A8] J. F. Benders, Partitioning procedures for solving mixed-variables programming problems, Numerische Mathematik. 4, 3 (Sept. 1962), pp. 238-252.
[A9] J. Hooker and G. Ottosson. Logic-based Benders decomposition. Mathematical Programming, Springer, 2003, 96 , 33-60

Author: Marco Chiarandini

Date: 2011-04-19 16:30:32 CEST

HTML generated by org-mode 6.36c in emacs 22