Algorithms for the Min-Max Regret Minimum Spanning Tree Problem

Abstract

Incerteza em optimização pode ser modelada com o conceito de cenários, onde cada cenário corresponde a um valor possível para cada parâmetro do problema. O critério do Min-Max Regret tem como objectivo encontrar uma solução que minimiza o máximo desvio, de entre todos os cenários, do valor óptimo de cada cenário. O estudo deste critério é motivado pelas aplicações práticas onde uma antecipação do pior caso é crucial. Problemas conhecidos, tais como o caminho mais curto e a árvore mínima de cobertura tornam-se NP-difícil com um critério Min-Max Regret. Actualmente, existe uma falta de conhecimento em como resolver estes problemas num modo eficiente. Este trabalho consiste em desenvolver algoritmos baseados no paradigma do Branch-and-Bound para resolver o problema da árvore de cobertura mínima num critério de Min-Max Regret. É realizada uma análise experimental, tal como a comparação com um algoritmo pseudo-polinomial recente. Os resultados experimentais mostram que, a abordagem realizada nesta dissertação tem melhor desempenho na maioria dos casos .

Uncertainty in optimization can be modelled with the concept of scenarios, where each scenario corresponds to possible values for each parameter of the problem. The Min-Max Regret criterion aims at obtaining a solution that minimizes the maximum deviation, over all possible scenarios, from the optimal value of each scenario. The study of this criterion is motivated by practical applications where an anticipation of the worst case is crucial. Well-known problems, such as the Shortest Path problem and the Minimum Spanning Tree become NP-hard with a Min-Max Regret criterion. Currently, there is a lack of knowledge on how to solve these problems in an efficient manner. This work consists in developing algorithms based on the Branch-and-Bound paradigm to solve the Minimum Spanning Tree problem under a Min-Max Regret criterion. An experimental analysis as well a comparison with a state-of-the-art pseudo-polynomial algorithm are also reported. The experimental results showed that this dissertation approach has better performance in most cases .