<- Archives UCL - Programme d'études ->



Constraint programming [ LINGI2365 ]


5.0 crédits ECTS  30.0 h + 15.0 h   2q 

Teacher(s) Deville Yves ;
Language English
Place
of the course
Louvain-la-Neuve
Prerequisites

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.

Main themes
  • 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)
Aims

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.
Evaluation methods
  • Projects (15% of the final grade)
  • Problem sets (25% of the final grade)
  • Written examn (60% of the final grade)
Teaching methods
  • lectures
  • practicals : 4 problem sets and 1 bigger project performed by group of 2
Content
  • 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
Bibliography

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.
Cycle et année
d'étude
> Master [120] in Computer Science and Engineering
> Master [120] in Computer Science
Faculty or entity
in charge
> INFO


<<< Page précédente