Constraint programming [ LINGI2365 ]

https://moodleucl.uclouvain.be/course/view.php?id=9158

• Constraints and domains
• Practical aspects of constraint solvers
• Constraint Satisfaction Problems (CSP)
• Models and languages for constraint programming
• Methods and techniques for constraint solving (consistency, relaxation, optimization, search, linear programming, global constraints, ...)
• Search techniques and strategies
• Problem modelling and resolution 
• Applications to differents problem classes (e.g. planification, scheduling, ressource allocation, economics, robotics)

Given the learning outcomes of the "Master in Computer Science and Engineering" program, this course contributes to the development, acquisition and evaluation of the following learning outcomes:

• INFO1.1-3
• INFO2.2-4
• INFO5.4-5
• INFO6.1, INFO6.4

Given the learning outcomes of the "Master [120] in Computer Science" program, this course contributes to the development, acquisition and evaluation of the following learning outcomes:

• SINF1.M4
• SINF2.2-4
• SINF5.4-5
• SINF6.1, SINF6.4

Students completing successfully this course will be able to

• explain and apply techniques for solving Constraint Satisfaction Problems
• solve simple problems involving CSP
• explain foundations of models and languages for constraint solving
• identify problem classes where constraint programming can be apply successfully
• model simple problems in the form of constraints, and express these models in a constraint programming language, including search strategies.

Students will have developed skills and operational methodology. In particular, they have developed their ability to:

• master rapidly a new programming language;
• use technical documents to deepen their knowledge of a topic.

The contribution of this Teaching Unit to the development and command of the skills and learning outcomes of the programme(s) can be accessed at the end of this sheet, in the section entitled “Programmes/courses offering this Teaching Unit”.

• Project (10% of the final grade)
• Problem sets (15% of the final grade)
• Written examn (60% of the final grade)

In case of failure of the note for projects + problems, the weighting of those parts will be greater.

Project and problem sets are mandatory during the semester of the course and cannot be repeated for the second examination session.

• lectures
• practicals : 2 problem sets and 1 bigger project performed by group of 2

• Introduction to constraint programming
• COMET: a constraint programming language
• Propagation
• Searching
• Modeling
• Designing constraints
• Global constraints
• Constraint programming and Mixed Integer programming
• Scheduling
• Continuous domain

References

• K. Apt. Principles of Constraint Programming. Cambridge University Press, 2003
• Rina Dechter. Constraint Processing. Morgan Kaufmann, 2004
• F. Rossi, P. Van Beek, T. Walsh (eds). Handbook of Constraint Programming.  Elsevier 2006.
• Kim Marriott, Peter J. Stuckey. Programming with Constraints. An Introduction.MIT Press, 1998.
• P. Van Hentenryck. The OPL Optimization Programming Language. The MIT Press, 1999.