Please use this identifier to cite or link to this item: https://hdl.handle.net/10316/83276
Title: Algorithms for the Min-Max Regret Minimum Spanning Tree Problem
Other Titles: Algoritmo para o problema da árvore de cobertura mínima usando o critério min-max com pesar
Authors: Godinho, Noé Paulo Lopes 
Orientador: Paquete, Luís Filipe dos Santos Coelho
Keywords: Min-Max Regret; Branch-and-Bound; Árvore de cobertura mínima; Optimização Combinatória; Avaliação de Desempenho; Min-Max Regret; Branch-and-Bound; Minimum Spanning Tree; Combinatorial Optimization; Performance Evaluation
Issue Date: 11-Jul-2017
Serial title, monograph or event: Algorithms for the Min-Max Regret Minimum Spanning Tree Problem
Place of publication or event: DEI-FCTUC
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 .
Description: Dissertação de Mestrado em Engenharia Informática apresentada à Faculdade de Ciências e Tecnologia
URI: https://hdl.handle.net/10316/83276
Rights: embargoedAccess
Appears in Collections:UC - Dissertações de Mestrado

Files in This Item:
File Description SizeFormat
Thesis.pdf692.17 kBAdobe PDFView/Open
Show full item record

Google ScholarTM

Check


This item is licensed under a Creative Commons License Creative Commons