Search and Optimization
Code
10799
Academic unit
Faculdade de Ciências e Tecnologia
Department
Departamento de Informática
Credits
6.0
Teacher in charge
Pedro Manuel Corrêa Calvente Barahona
Weekly hours
4
Total hours
54
Teaching language
Português
Objectives
This course focuses on the study of combinatorial problems (satisfaction and/or optimization), particularly in their modeling and solving methods. It adopts a declarative programming paradigm, where the declaration of restrictions is specified separately from the resolution. The resolution of these problems can be addressed from two complementary or alternative perspectives: a) complete search, with backtracking, providing guarantees of completeness but with limitations on the size of the problems addressed, and b) local search, not offering such guarantees but enabling a resolution (approximate) of larger problems.
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 methods of resolution are best suited given the characteristics of the problem, and c) what limitations are imposed by the combinatorial nature of the problem.
Subject matter
1. Decision and Optimization Problems.
- Declarative constraint modelling
- Types of constraints: Table, Arithmetic, Disjunctive, Reified, Global
- Complexity
2. Complete Methods for Constraint Solving/Backtrack search
- Constraint networks
- Local consistencies (node, arc, domain/bounds)
- Nonlocal consistencies (Path, k )
- Algorithms to maintain them.
- Search heuristics
- Variable and value Selection
- General purpose heuristics (dom, deg, dom/wdeg, impact)
- Optimisation - branch & bound
3. Incomplete Methods/Constrained-Based Local Search
- Invariants and differentiable objects.
- Degree of satisfaction of constraints
- Heuristics
- Variable-based vs. constraintbased
- Greedy vs. stochastic
- Meta-heuristics
- Restarts, Taboo search, Simulated annealing
- Variable and Large neighbourhoods
- Ant colony optimisation
Bibliography
Text Books
• Dina Rechter, Constraint Processing, Morgan Kauffman, 2003.
• Pascal Van Hentenryck and Laurent Michel, Constraint-Based Local Search, MIT Press, 2009.
Manuals
• Comet Tutorial, Dynamic Decision Technologies Inc., August 28, 2009
Additional Reading
• Handbook of Constraint Programming, F. Rossi, P. van Beek & T. Walsh (eds), Elsevier Science, 2008
Evaluation method
Evaluation (throughout the semester) consists of 4 components: 2 Projects and 2 Mini-tests, all graded 0-20, and with the same weight (25%) on the final grade. Students must have a minimum of 6/20 in both the averages of the tests/exams and the projects.
Projects are made in teamwork (2 students per group) and the mini-tests assess the students individually. Students that do not get the minimum grade, are allowed to do a repeat exam if they get at least an average grade of 6/20 in the two projects.
The components of the assessment cover the topics shown below (together with the dates):
Project_1 – Constraint Programming Problem (21 October to 9 November)
Mini-Test_1 – Constraint Programming Concepts (31 October )
Project_2 – Constrained Local Search Problem (25 November to 14 December)
Mini-Test 2 – Constrained Local Search Concepts (12 December)
The marks obtained in the final exam replace those obtained in the 2 mid-term tests (if better).
Exam – Constraint Programming and Constrained Local Search Concepts (date to be announced)