1. Home
  2. NOVA School of Science and Technology
  3. Computer Science and Engineering
  4. Constraint Programming

Constraint Programming

Objectives

Knowledge:

  • Constraint Satisfaction Problems, and its combinatorial complexity.
  • Discrete (finite and Boolean) and continuous domains. The special case of SAT.
  • Constraint propagation and types of consistency.
  • Algorithms for consistency maintenance.
  • Heuristics.

Application:

  • Problem modelling and solving.
  • Selection of the most adequate constraints and algorithms.
  • Choice of efficient heuristics.

Soft-skills:

  • Understanding of informal specifications.
  • Identification of the most adequate models.
  • Abstraction and generalisation skills.
  • Analysis and explanation of results.
  • Specialised literature search
 

General characterization

Code

11164

Credits

6.0

Responsible teacher

Jorge Carlos Ferreira Rodrigues da Cruz, Pedro Manuel Corrêa Calvente Barahona

Hours

Weekly - 4

Total - 54

Teaching language

Português

Prerequisites

Available soon

Bibliography

Main References:

  1. Dina Rechter, Constraint Processing, Morgan Kauffman, 2003.
  2. Krzysztof Apt, Principles of Constraint Programming, Cambridge University Press, 2009 (online)
  3. Jaulin, L., Kieffer, M., Didrit, O., Walter, E., Applied Interval Analysis, Springer, 2001.
  4. Eldon Hansen, G. William Walster, Global Optimization Using Interval Analysis, Marcel Dekker, 2003
  5. Jorge Cruz, Constraint Reasoning for Differential Models, 126 Frontiers in Artificial Intelligence and Applications, IOS Press, 2005.

Complementary Reference:

  1. Comet Tutorial, Dynamic Decision Technologies Inc., August 28, 2009.
  2. Handbook on Constraint Programming, (F. Rossi, P. van Beek and T. Walsh, eds.), Elsevier, 2006
  3. Handbook of Satisfiability, (A. Biere, M. Heule, H. Van Maaren and T. Walsh, eds.), IOS Press, 2009
  4. 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 their implementation in the modelling and execution languages and systems adopted.

The laboratory classes are dedicated to solving problems, selected from typical benchmarks in these áreas, in order to exploit and develop adequate models and search techniques.

Evaluation method

The assessment and grading of students includes:

  • 2 mini tests (on discrete and finite domains), where the knowledge acquired by the students on the concepts and characteristics of the search techniques are assessed.
  • 2 practical projects, that focus on the resolution of mid-sized constraint problems (on discrete and finite domains), and assess the ability of the students to problem modelling and the use and adaptation the techniques explored in the lab classes, albeit in simpler problems.

The final grade is the average of these 4 components, a minimum grade of 8.0 being required both in the average of the 2 mini-tests and in the average of the practical projects.

The grade of the theoretical tests can be replaced by the grade obtained in the final exam.Only students with an average of grades of the practical projects no less than 8.0 have access to the final exam.

Both tests and examination (open book) will be done in person if  sanitary (COVID-19) conditions permit.

Subject matter

1. Decision problems in discrete domains.
2. Problem Modelling.
3. Problem Solving.
4. Introduction to Interval Constraints.
5. Continuous Constraints and Interval analysis.
6. Interval Newton Method.
7. Associating Narrowing Functions to Constraints.
8. Constraint Propagation and Consistency Enforcement.
9. Problem Solving in Continuous Domains.

Programs

Programs where the course is taught: