ARTIFICIAL INTELLIGENCE FOR CONSTRAINED OPTIMIZATION
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
- 2022/2023
- Teacher
- MARCO GAVANELLI
- Credits
- 6
- Didactic period
- Secondo Semestre
- SSD
- ING-INF/05
Training objectives
- This course studies algorithms and languages based on artificial intelligence to solve problems of satisfiability and constrained optimization.
The teaching objectives of the course are that students are able to
- describe the main characteristics of a constraint logic programming language on finite domains (CLP(FD))
- describe the propagation algorithms of the main constraints in CLP(FD)
- model a constraint satisfaction problem or a constraint optimization problem in CLP(FD), Answer Set Programming, MiniZinc
- describe the algorithm of a conflict-directed clause learning SAT solver
- encode a constraint satisfaction problem into SAT
- recognize which constraint models are more promising than others 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 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 languages and programming constraints Answer Set Programming.
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.
Constraint Logic Programming on Finite Domains
- Global constraints
- Optimization
- Generation of new constraints
- symmetry breaking, redundant constraint
- search strategies
- applications of constraint logic programming to real problems
The MiniZinc language
SAT resolution algorithms
- Davis-Putnam-Logemann-Loveland algorithm
- Conflict-Directed Clause Learning
Encoding constraint satisfaction problems into SAT
- direct encoding
- log encoding
- support encoding
Answer Set Programming Didactic methods
- The course is organized as a Flipped Classroom: video lessons on all the topics of the course are provided to the students that can watch them at home.
The face-to-face lessons are held in the computer lab; exercises are assigned and students will solve them on the computer, in order to learn the techniques learned in the video-lessons through "learning by doing".
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.
To the students attending the course, exercises will be assigned and will be corrected by the professor. 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.
During the lab test, students can access the documentation about the software studied in the course; it is not possible to consult other material (notes, slides, etc.).
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).
During the written test it is not possible to consult any material.
The final grade is the sum of the votes in the two parts.
If requested at least one week in advance, the exam can be given in English. Reference texts
- The reference material is published on the Google Classroom (with code swtkeqg for the academic year 2022/23)
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
