Constraint Programming
Code
11164
Academic unit
Faculdade de Ciências e Tecnologia
Department
Departamento de Informática
Credits
6.0
Teacher in charge
Francisco de Moura e Castro Ascensão de Azevedo, Pedro Manuel Corrêa Calvente Barahona
Weekly hours
4
Total hours
46
Teaching language
Inglês
Objectives
This course focuses on the study of constraint problems on continuous domains), particularly in their modeling and solving methods. It adopts a declarative programming paradigm, where the declaration of constraints is specified separately from their resolution. Solving of these problems is based on constraint propagation, using different techniques to reduce search space and using nterval arithmetics for continuous domais to narrow the intervals where solutions can be found.
It is expected that the successful student of this course will obtain significant knowledge and experience on the modeling and resolution of this type of problems, identifying for a given problem, a) which are the best models to adopt in its specification, b) which propagation methods are best suited given the characteristics of the problem, and computer tools that implement them.
Prerequisites
Basic knowledge of programming, logic programming, constraints, and combinatorial search.
Subject matter
1. Constraint Satisfaction Problems: Basic Concepts
Variables, domains and solutions
Sets
Continuous domains: intervals
2. Sets
Sets and multisets: relations, operations, and functions
Modeling
Set variables: representation, domains, set intervals, cardinality
Set constraint solvers: Cardinal, and others
3. Cardinal
Operational semantics
Labeling
Examples and applications
4. Optimisation
Branch and bound
Cardinal extensions
Extended logic
Local search for digital circuits
5. Continuous Domains and Interval Arithmetic
Representation of continuous domains
Interval arithmetic
Interval functions
Interval Newton method
6. Associating Narrowing Functions to Constraints
Projection function and their enclosure
Constraint decomposition method
Constraint Newton method
Complementary approaches
7. Constraint Propagation and Consistency Enforcement
Consistency Types
Arc, interval, hull and box consistencies
Constraint Propagation
Narrowing Functions and their Properties
Constraint Propagation Algorithm and its Properties
8. Problem Solving
Modelling techniques
Some Languages and Tools
Benchmarking
Typical benchmarks
Bibliography
• Francisco Azevedo, Constraint Solving over Multi-valued Logics - Application to Digital Circuits, vol 91 of Frontiers of Artificial Intelligence and Applications, ISBN: 1 58603 304 2, IOS Press, xviii + 204 pages, 2003.
(Basically chapters 6 and 7)
• Francisco Azevedo, Cardinal: A Finite Sets Constraint Solver, in Constraints journal, Volume 12, Number 1, Springer, pages 93-129, 2007.
• Jorge Cruz, Constraint Reasoning for Differential Models, 126 Frontiers in Artificial Intelligence and Applications, IOS Press, 2005
• Eldon Hansen, G. William Walster, Global Optimization Using Interval Analysis, Marcel Dekker, 2003
• Jaulin, L., Kieffer, M., Didrit, O., Walter, E., Applied Interval Analysis, Springer, 2001
• Ramon E. Moore, Interval Analysis, Prentice-Hall, 1966
Teaching method
The syllabus is taught in theoretical and laboratory classes. In the former, the main concepts and techniques are addressed, together with possible implementations.
The laboratory classes address these implementations, using two constraint solver tools (for sets and continuous constraints), exploiting models and techniques made available by the tools, namely in the elaboration of the projects.
Evaluation method
Assessment (throughout the semester) consists of 4 components: 2 written tests and 2 projects, with 50-50% weights for the theoretical and practical parts.
Tests and projects are individual, although a project may be done in groups of 2 students, if agreed with the lecturer.
To be granted "frequency", students must have an average of at least 10 points, in the projects component. Approval of the course requires frequency and no less than 10 points in the weighted average of the 4 assessment components.
Students with frequency are admitted to the final exam, whose grade, if better, replaces the grading of the tests.