CONSTRAINT PROGRAMMING
Academic year and teacher
If you can't find the course description that you're looking for in the above list,
please see the following instructions >>
- Versione italiana
- Academic year
- 2018/2019
- Teacher
- MARCO GAVANELLI
- Credits
- 6
- Didactic period
- Secondo Semestre
- SSD
- ING-INF/05
Training objectives
- The main objective of the course consists in providing students knowledge about the main declarative languages based on constraints and providing students the ability to model problems with constraints in the main constraint languages.
The course presents the main techniques of constraint propagation and constraint solving, together with their practical application to various types of real problems.
In particular, the course covers the languages ¿¿and solvers over finite domains, with hints of languages and solvers
on real numbers and other domains. Particular emphasis will be given to languages based on logic, such as Constraint Logic Programming and Answer Set Programming languages.
The main techniques used in SAT solvers will be presented, as well as techniques to encode constraints problems in SAT. Constraint Modeling languages, such MiniZinc, will be presented.
The main acquired knowledge relates to:
• Constraint solving techniques
• constraint programming languages ¿¿and constraint modeling languages
• modeling of problems in constraint and logic languages
The main skills (i.e. the ability to apply the acquired knowledge) are:
• resolution of a problem by means of a constrained model in various logic-based programming languages Prerequisites
- To attend the course, it is necessary to have acquired the following knowledge, provided by the course "Fundamentals of Artificial Intelligence"
• logic programming
• constraint satisfaction problems and their solution methods Course programme
- The course includes 60 hours of lectures in the classroom and in the lab, on the following main topics:
Constraint Logic Programming
The MiniZinc language
Algorithms of SAT resolution and coding in the SAT
Answer Set Programming Didactic methods
- The course consists of 60 hours; part of the lessons are in classroom and part in the computer science laboratory.
The lessons cover the topics of the course, and include guided computer exercises.
The laboratory exercises involve the use of constraint logic programming languages, constraint modelling languages, SAT solvers and Answer Set Programming languages for the solution of constraint problems. Learning assessment procedures
- The aim of the examination is to test the level of achievement of the previously mentioned educational goals.
In order to test the ability of the student to model a constraint problem into the various languages studied during the course, students have to pass a laboratory test; in such a test, the student is given a problem, and (s)he has to solve it through a program either in Answer Set Programming or in MiniZinc, and (s)he also has to solve it in Constraint Logic Programming.
In this part, students can get up to 25 points (out of 30); an evaluation around 25 in this test shows that the student got excellent capacity to model problems with constraints and using different constraint languages, while an evaluation around 13 means that student's modeling and solving skills with constraints are sufficient.
In order to test the knowledge of the students on the propagation techniques available in modern solvers, a written test is performed. This test contains an exercise in which students show to know the propagation techniques in constraint logic programming using global constraints (typically, 4 points out of 30 are reserved for this exercise) and an exercise on the solution of problems in SAT (typically, 4 points out of 30).
The final grade is the sum of the votes in the two parts.
Upon request, the exam can be given in English Reference texts
- The reference material includes:
- copy of the slides, available on the course web site
- on-line manuals of the used software (ECLiPSe, MiniZinc, clasp)
For further information, we recommend the following books:
- Krzysztof R. Apt and Mark Wallace. Constraint Logic Programming using Eclipse. Cambridge University Press, 2007
- Francesca Rossi, Peter van Beek, Toby Walsh (Eds.):
Handbook of Constraint Programming, Elsevier 2006
- Martin Gebser, Roland Kaminski, Benjamin Kaufmann, Torsten Schaub: Answer Set Solving in Practice. Morgan & Claypool, 2012
