Please use this identifier to cite or link to this item:
http://hdl.handle.net/1843/35412
Type: | Tese |
Title: | The Minmax regret 0-1 integer linear programming problem under interval uncertainty: complexity and heuristics |
Other Titles: | O problema de otimização inteira 0-1 Minmax regret sob incerteza intervalar: complexidade e heurísticas |
Authors: | Iago Augusto de Carvalho |
First Advisor: | Thiago Ferreira de Noronha |
First Co-advisor: | Christophe Didier Duhamel |
First Referee: | Rafael Castro de Andrade |
Second Referee: | Vinícius Fernandes dos Santos |
Third Referee: | Cristiano Arbex Valle |
metadata.dc.contributor.referee4: | Puca Huachi Vaz Penna |
Abstract: | Minmax regret é um framework para abordar incerteza no processo de tomada de decisão. Nesta tese, nós investigamos problemas de otimização minmax regret onde o coeficiente das variáveis da função objetivo é desconhecido, mas é assumido ser restrito por um intervalo. O Problema da Programação Linear Inteira 0-1 Minmax regret sob Incerteza Intervalar (M-ILP) é investigado. Nós provamos que este problema é completo para o segundo nível da hierarquia polinomial, sendo \Sigma^p_2-Completo. Além disso, nós introduzimos as heurísticas \textit{Fix-and-Optimize} (FAO), que podem ser generalizadas para qualquer problema de otimização minmax regret sob incerteza intervalar. Nós avaliamos a qualidade das heurísticas propostas realizando experimentos computacionais em duas instâncias de M-ILP: o problema da Cobertura de Conjuntos Ponderado Minmax regret sob Incerteza Intervalar e o Problema do Caminho Mais Curto de Fonte Única Minmax regret sob Incerteza Intervalar. Para o primeiro, nós mostramos que ele está contido na classe \Sigma^p_2. Além disso, nós extendemos algoritimos exatos baseados na Decomposição de Benders para este problema, propomos duas variantes das heurísticas FAO e comparamos os resultados obtidos com os resultados da literatura para este problema. Para o último, nós mostramos que o problema é NP-Difícil mesmo em digrafos em camadas com 3 camadas, obtemos soluções ótimas resolvendo uma formulação \textit{multi-commodities} usando um algoritmo branch-and-bound, e implementamos as duas mesmas variações das heurísticas FAO. Os resultados obtidos pelas heurísticas FAO também são comparados com os resultados das heurísticas estado-da-arte para este problema. Experimentos computacionais realizados em instâncias clássicas da literatura demonstraram que uma das heurísticas FAO propostas é significativamente melhor que as heurísticas da literatura quando resolvendo ambos os problemas estudados. |
Abstract: | Minmax regret is a framework to tackle uncertainty in the decision-making process. In this thesis, we investigate minmax regret optimization problems where the coefficient of the variables on the objective function is unknown, but it is assumed to be bounded by an interval. The Minmax regret 0-1 Integer Linear Programming Problem under Interval Uncertainty (M-ILP) is investigated. We prove that this problem is complete for the second level of the polynomial hierarchy, being \Sigma^p_2-Complete. Furthermore, we introduce the Fix-and-Optimize (FAO) heuristics, which can be generalized for any minmax regret optimization problem under interval uncertainty. We assess the quality of the proposed heuristics by performing computational experiments on two instances of M-ILP: the Minmax regret Weighted Set Covering Problem under Interval Uncertainty and the Minmax regret Single-Source Shortest Path Problem under Interval Uncertainty. For the former, we show that it is contained in the class \Sigma^p_2. Furthermore, we extend exact algorithms based on the Bender's Decomposition for this problem, propose two variants of the FAO heuristics, and compare the obtained results with those of the literature for this problem. For the latter, we show that the problem is NP-Hard even on a layered digraph with 3 layers, obtain optimal solutions by solving a compact multi-commodities formulation using a branch-and-bound algorithm, and implement the same FAO heuristic variants. The results obtained by the FAO heuristics are also compared with those of the state-of-the-art heuristics for this problem. Computational experiments performed on classical instances from the literature demonstrated that one of the proposed Fix-and-Optimize heuristics significantly outperformed the literature heuristics for solving both of the studied problems. |
Subject: | Computação – Teses. Complexidade computacional – Teses. Incerteza intervalar – Tese. Heurística – Teses |
language: | eng |
metadata.dc.publisher.country: | Brasil |
Publisher: | Universidade Federal de Minas Gerais |
Publisher Initials: | UFMG |
metadata.dc.publisher.department: | ICX - DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO |
metadata.dc.publisher.program: | Programa de Pós-Graduação em Ciência da Computação |
Rights: | Acesso Aberto |
metadata.dc.rights.uri: | http://creativecommons.org/licenses/by-sa/3.0/pt/ |
URI: | http://hdl.handle.net/1843/35412 |
Issue Date: | 30-Jan-2020 |
Appears in Collections: | Teses de Doutorado |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
tese_final_biblioteca.pdf | Tese | 13.66 MB | Adobe PDF | View/Open |
This item is licensed under a Creative Commons License