Advanced Module : Constraints
 • Reference: EMCL-A-C
 • Courses:
• CP - Constraint Programming
• DAOP - Design of Algorithms for Optimisation Problems
• Requirements:
To obtain the 12 crs of the module, students should obtain 6 crs in each of the two courses.
• Description:
The module aims to provide the students with theoretical and practical knowledge on solving combinatorial problems, exploring their declarative modelling with Constraint (Logic) Programming languages and advanced methods to solve them efficiently.
The module addresses various types of domains for the variables of these problems, namely finite and continuous domains, and analyses their specificities as well as commonalities. The worst case and typical complexity of the underlying propagation algorithms is studied, together with their integration with both complete backtrack search and local search algorithms. In addition, some extensions of the pure constraint satisfaction paradigm are studied, namely optimization, soft constraints and universally quantified problems.

-------------------------------------
CP - Constraint Programming
• Reference: 11164
• Semester: Autumn
• Web Page: ssdi.di.fct.unl.pt/pr
• Lecturers: Pedro Barahona and Jorge Cruz
• 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.

-------------------------------------
DAOP - Design of Algorithms for Optimization Problems
• Reference: 11556
• Semester: Spring
• Web Page: ssdi.di.fct.unl.pt/dapo
• Lecturers: Pedro Barahona, Margarida Mamede and Fernanda Barbosa
• Description:
Optimization problems are crucial in a wide range of areas of activity. However, in general, its exact resolution is not possible due to their complexity and to the size of instances in real applications. In this context, there are various design techniques that allow the development of very competitive algorithms, namely:
(a) Approximation Algorithms, for which the maximum error between the solution found and the optimal solution can be calculated;
(b) Randomized Algorithms, for which one can characterize either the likelihood of the solution found with limited resources to be optimal, or the probability that the algorithm requires reasonable resources to find the optimal solution;
(c) Local Search Algorithms that, in spite of not offering the guarantees of the previous algorithms, often obtain better solutions with a good compromise with respect to the resources used.
In this course we study several of these algorithms and their application to various optimization problems, so that students can explore different methods and seize the advantages and disadvantages of each one of them.