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

Teofilo F. Gonzalez (Ed.). Handbook of Approximation Algorithms and Metaheuristics, Second Edition: Methodologies and Traditional Applications. CRC Press, 2018.

Patrick Siarry (Ed.). Metaheuristics. Springer, 2016.

Rafael Martí, Pardalos Panos, and Maurício Resende (Eds.). Handbook of Heuristics. Springer, 2017

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 Components

Assessment has two components: the laboratory component and the theoretical-practical component.

Laboratory Component

The laboratory component comprises one project done in teams of two students. It 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 (which occurs at the end of the semestre).

The laboratory component grade (LComp) is the mean of the two project phase grades (P1 and P2):

LComp = (P1 + P2) / 2.

In order to succeed (and to have access to the exam), it is required that LComp >= 9.

Theoretical-Practical Component

The theoretical-practical component comprises two tests. If the mean of the test grades is less than 9 and LComp >= 9, students can do a final exam. The tests and the exam are written, open-book, and done individually in person.

The theoretical-practical component grade (TPComp) is the mean of the test grades (T1 and T2) or the exam grade (Ex):

TPComp = (T1 + T2) / 2   or   TPComp = Ex.

In order to succeed, it is required that TPComp >= 9.

Final Grade

The final grade (F), defined only if LComp >= 9, is:

  • F = TPComp,   if TPComp < 9;
  • F = (LComp + TPComp) / 2,   if TPComp >= 9.

All grades (P1, P2, T1, T2, Ex, LComp, and TPComp) are rounded to the nearest tenth, except the final grade (F) which is rounded to the nearest whole number.

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.

Programs

Programs where the course is taught: