Constraint programming [ LINGI2365 ]

Basic concepts and methods in Artificial Intelligence (e.g. INGI2261)

Students who did not follow this course should ask permission to the instructor to follow the class.

• Constraints and domains
• 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)

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 (15% of the final grade)
• Problem sets (25% of the final grade)
• Written examn (60% of the final grade)

• lectures
• practicals : 4 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

slides online

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.