Titulo Estágio
Algorithms for the Min-Max Regret Minimum Spanning Tree Problem
Áreas de especialidade
Sistemas Inteligentes
Local do Estágio
ECOS/DEI
Enquadramento
Uncertainty in optimization can be structured through the concept of scenario that corresponds to an assignment of plausible values to model parameters.
The min–max regret criterion aims at obtaining a solution minimizing the maximum deviation, over all possible scenarios, from the optimal value of the corresponding scenario. The study of these criteria is motivated by practical applications where an anticipation of the worst case is crucial. More formally, the min-max regret criterion is defined as
min_{x in X} max_{s in S} ( f(x,s) – f(x*,s) )
where X is the set of solutions, S is the set of all scenarios, f(x,s) is the value of a solution x under scenario s and f(x*,s) is the optimal value under scenario s.
Well-known problems, such as shortest path problem and minimum spanning tree, become NP-hard with a min–max regret criterion. Currently, there is a lack of knowledge on how to solve those problems in an efficient manner.
Objetivo
This work consists of developing algorithms based on implicit enumeration strategies (such as branch-and-bound) to solve the minimum spanning tree problem under a min–max regret criterion. Note that the optimal solution for this problem can be efficiently computed for one scenario, using Kruskal or Prim algorithm, but it is no longer the case with several scenarios under a min–max regret formulation. The student should experimentally evaluate the performance the algorithms developed in this project on a wide range of instances. Other problem variants should be considered if time allows.
Plano de Trabalhos - Semestre 1
- Literature review: Notions of graphs and combinatorial optimization, algorithms for the minimum spanning tree problem, branch-and-bound, min-max regret criterion.
- Development of Kruskal or Prim algorithm
- Development of upper and lower bounds for the minimum spanning tree problem
- Preliminary experimental evaluation
- Writing of the intermediate report
Plano de Trabalhos - Semestre 2
- Development of Branch-and-Bound for the mimimum spanning tree problem under min-max regret criterion
- Experimental evaluation
- Study of particular variants (e.g. constrained versions)
- Writing of the final report
Condições
This MSc project is for students that would like to deepen his knowledge on algorithms and combinatorial optimization. The MSc student can use the computational resources from ECOS group for performing experiments. This project has no funding available.
Observações
Hassene Aissi and Cristina Bazgan and Daniel Vanderpooten, Min–max and min–max regret versions of combinatorial optimization problems: A survey, European Journal of Operational Research, 197(2), 427 – 438, 2009.
Orientador
Luís Paquete
paquete@dei.uc.pt 📩