Design of Algorithms for Optimization Problems
Objectives
Optimization problems are central in several areas of activity but their exact resolution is generally not possible due to their combinatorial nature (NP-hard complexity) and the size of the instances in real applications. In this context, there are several algorithm design techniques which, in spite of not guaranteeing exact solutions, lead to very competitive algorithms, not only for their efficiency, but also for some guaranted properties regarding the acceptable solutions they obtain with limited resources, namely:
Polynomial Approximation Algorithms compute approximate solutions, in the sense that an upper bound of the error between the computed solution and the optimal solution can be determined. Randomized approximation algorithms, exploring the randomness in generating solutions, provide guarantees on the probability of the amount of resources needed to obtain approximate solutions.
Local Search Algorithms that, although not offering formal guarantees of the previous algorithms, allow to obtain very good solutions, often with a good compromise with the necessary resources to acquire it.
This UC addresses several such algorithms and their application to various problems, so that students can explore different methods to solve optimization problems and grasp the advantages and disadvantages of the alternatives studied.
General characterization
Code
11556
Credits
6.0
Responsible teacher
Margarida Paula Neves Mamede, Pedro Manuel Corrêa Calvente Barahona
Hours
Weekly - 4
Total - 55
Teaching language
Português
Prerequisites
Students should:
(a) Be proficient in programming;
(b) Be familiar with the fundamental data structures (linked lists, hash tables, binary search trees, binary heaps);
(c) Be able to calculate the time and the space complexities of algorithms;
(d) Know the basic concepts of search in state spaces.
Bibliography
Main References:
Jon Kleinberg and Éva Tardos. Algorithm Design. Addison-Wesley, 2005.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms (3rd ed.). MIT Press, 2009.
Pascal van Hentenryck and Laurent Michel. Constraint-Based Local Search. MIT Press, 2005.
Complementary References:
Anany Levitin. Introduction to The Design and Analysis of Algorithms (3rd ed.). Addison-Wesley, 2012.
Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-completeness. W. H. Freeman and Company, 1979.
Teaching method
There are two hours of lectures and a lab session each week. In the laboratory, students design, analyse and implement algorithms.
Evaluation method
Assessment comprises one programming project and two tests.
The programming project is developed in two phases, whose deadlines are distinct, and consists of a theoretical and experimental comparative study of alternative solutions for an optimization problem, including the writing of two reports (one on each phase) and a discussion. The tests and the exam are open-book.
Condition to succeed:
Pgrade >= 9 and Tgrade >= 9 and Fgrade = (Pgrade + Tgrade) / 2 >= 10,
where
- Pgrade is the project grade, calculated with the two phase grades;
- Tgrade is the mean of the test grades or the exam grade;
- Fgrade is the final grade.
In case of failure, if the project grade is not less than 9 (out of 20), students can do a final exam, whose grade replaces the previous Tgrade.
Subject matter
1. Decision problems and optimization problems. Tractable problems and hard problems. Algorithm design techniques for hard optimization problems.
2. Approximation algorithms. Approximation ratio. Greedy strategies. Approximation schemes. Linear programming and rounding. The primal-dual method. Randomized approximation algorithms. Probabilistic analysis.
3. Local search algorithms. Restarts. Taboo search. Simulated annealing. Variable neighbourhood search. Ant colony optimization. Hybrid Evolutionary Search. Guided Local Search. Large neighbourhood search.