Design of Algorithms for Optimization Problems (2017/2018) - Departamento de Informática
Description

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.

This UC addresses several such algorithms (approximation and local search) 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.

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.

Syllabus

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.

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 edition). The 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 edition). Addison-Wesley, 2011.

Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-completeness. W. H. Freeman and Company, 1979.

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.

Student work
  Hours per credit 28
  Hours per week Weeks Hours
Aulas práticas e laboratoriais   26.0
Aulas teóricas   26.0
Avaliação   5.0
Self study   48.0
Orientação tutorial   3.0
Project   60.0
Total hours 168
ECTS 6.0