Constraint programming [ LINGI2365 ]

> https://icampus.uclouvain.be/claroline/course/index.php?cid=INGI2365

• 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.

• Projects (10% of the final grade)
• Problem sets (15% of the final grade)
• Written examn (75% of the final grade)

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

The problem sets and the project must be submitted and may be realized only during the quadrimester of the course.

It is not possible to realize them during another quadrimster or for the exam resset of September.

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

• Introduction to constraint programming
• Modeling
• Propagation
• Searching
• Global constraints
• Constraint programming optimization
• Known issues in CP and solution of new problems
• Pratical aspects of constraint solvers

References

• C. Lecoutre, Constraint Networks, Wiley, 2009
• 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.

Background:

• LINGI2261 : Basic concepts and methods in Artificial Intelligence