Constraint programming

lingi2365  2017-2018  Louvain-la-Neuve

Constraint programming
5 credits
30.0 h + 15.0 h
Q2
Teacher(s)
Deville Yves; Schaus Pierre (compensates Deville Yves);
Language
English
Main themes
  • 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)
Aims

At the end of this learning unit, the student is able to :

1

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”.
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
Teaching methods
  • lectures
  • practicals : 2 problem sets and 1 bigger project performed by group of 2
Evaluation methods
  • 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.
Online resources
https://moodleucl.uclouvain.be/course/view.php?id=9158
Bibliography
Livres de référence
  • 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.
Faculty or entity
INFO


Programmes / formations proposant cette unité d'enseignement (UE)

Title of the programme
Sigle
Credits
Prerequisites
Aims
Master [120] in Data Science Engineering
DATE2M
5
Master [120] in Computer Science and Engineering
INFO2M
5
Master [120] in Computer Science
SINF2M
5
Master [120] in data Science: Information technology
DATI2M
5