Constraint Programming (2016/2017) - Departamento de Informática

Additional information: http://pr.ssdi.di.fct.unl.pt

Description

This course, offered to the Integrated Master in Computer Science and Engineering and to the European Master''''''''s Program in Computational Logic, deepens the knowledge on the topic of Search, listed as optional in the 2008 ACM CS Curriculum in the field of Intelligent Systems (IS / AdvancedSearch [elective]), and its use for solving combinatorial problems.

Combinatorial problems (both satisfaction and/or optimization) are common in many application domains (resource management, scheduling, timetabling) including computer science itself (eg hardware/software configuration, program verification). The complexity of combinatorial problems require the use of efficient methods of resolution, studied in this course unit, and based on complete search in finite (or Boolean) domains, constraint propagation to narrow the variable domains during search. The course also addresses constraint propagation adapted for continuous domains, although in this case the completeness of search cannot be generally guaranteed.

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
Syllabus

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.

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
Student work
  Hours per credit 28
  Hours per week Weeks Hours
Aulas práticas e laboratoriais   24.0
Aulas teóricas   24.0
Avaliação   6.0
Self study   54.0
Orientação tutorial   6.0
Project   54.0
Total hours 168
ECTS 6.0