Resultados sobre o Problema da Floresta Restrita de Peso Mínimo
Autores
|
7428 |
3227,539
|
|
|
7429 |
3227,539
|
Informações:
Publicações do PESC
Apresentam-se, nesta tese, abordagens e resultados teóricos sobre o Problema da Floresta Restrita de Custo Mínimo (PFR). No contexto do PFR, o principal objetivo é identificar uma floresta geradora do grafo de entrada, tal que a soma dos pesos de suas arestas seja mínimo, e cada componente conexa contenha pelo menos k vértices.
Na parte teórica do nosso trabalho realizamos um estudo de dominância com modelos existentes na literatura, bem como apresentamos um teste de redução para instâncias do problema. No escopo prático, propomos três novas formulações de programação linear inteira, onde uma delas, com modelagem direcionada, foi capaz de superar o atual estado-da-arte do problema. Além disso, propomos heurísticas para resolver mais eficientemente o problema de separação de desigualdades exponenciais presentes na literatura e nos modelos propostos.
Ademais, apresentamos quatro novas formulações baseadas em decomposições, sendo duas decomposições lagrangianas e duas decomposições do tipo Dantzig-Wolfe. As decomposições lagrangianas demonstraram potencial quando utilizadas como pré-processamento para nosso algoritmo de Branch-and-Cut. As reformulações do tipo Dantzig-Wolfe ainda apresentam subproblemas caracterizados como NP-Díficil, e portanto sua motivação se limita à busca de melhores limites duais. Finalmente, apresentamos duas heurísticas primais baseadas nas metaheurísticas de Colônia de Formigas e Greedy Randomized Adaptive Search Procedure.
This thesis presents approaches and theoretical results for the Constrained Forest Problem (CFP). In the CFP context, the main objective is to identify a spanning forest of the input graph, such that the cumulative weight of the selected edges is minimal, and that each connected component spans at least k vertices.
In the theoretical part of our work, we conducted a dominance study with existing models in the literature, as well as presented a reduction test for problem instances. In the practical scope, we proposed three new integer linear programming formulations, one of them uses arc variables and was able to outperform the current state-of-the-art for the problem.
In addition, we proposed efficient heuristics to solve the separation problem for exponential inequalities, which are present in the literature and in our proposed models. Also, we propose four new formulations that are decomposition-based, two of them are Lagrangian decompositions and the other two are Dantzig-Wolfe decompositions. The Lagrangian decompositions demonstrated potential when used as preprocessing for our Branch-and-Cut algorithm. The Dantzig-Wolfe reformulations still had NP-hard subproblems, and therefore their motivation is limited to the search for better dual bounds. Finally, we present two primal heuristics based on the Ant Colony and Greedy Randomized Adaptive Search Procedure metaheuristics.