Algorithms for the Min-Max Regret Minimum Spanning Tree Problem

Authors

Abstract

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.

Keywords

min-max regret, branch-and-bound, minimum spanning tree, combinatorial optimization, graph algorithms, performance evaluation

MSc Thesis

Algorithms for the Min-Max Regret Minimum Spanning Tree Problem, July 2017

PDF File

DOI