Novos algoritmos, heurístico e exato, para o MWPSP

• Ano de defesa: 2021
• Autor(a) principal: Kataki, Paulo Augusto Gomes
• Orientador(a): Longo, Humberto José
• Banca de defesa: Longo, Humberto José, Santana, Márcia Rodrigues Cappelle, Silva, Hebert Coelho da, Pecin, Diego Galindo
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal de Goiás
• Programa de Pós-Graduação: Programa de Pós-graduação em Ciência da Computação (INF)
• Departamento: Instituto de Informática - INF (RG)
• País: Brasil
• Palavras-chave em Português: MWPSP; Branch-and-cut; Algoritmo exato; Heurística primal-dual; Operação topológica
• Palavras-chave em Inglês: MWPSP; Branch-and-cut; Exact algorithm; Primal-dual heuristic; Topological moves
• Área do conhecimento CNPq: CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
• Link de acesso: http://repositorio.bc.ufg.br/tede/handle/tede/11296

This project is the result of a wide study on the Maximum Weight Planar Subgraph Problem (MWPSP), which belongs to the NP-hard class of optimization problems. This problem is important in modeling and solving problems, such as the facility location, integrated circuit design, architectural design, analysis of financial data and biological systems. The text lists the main currently available heuristic and exact algorithms for the resolution of the MWPSP, planarity tests, and some of the main topological moves used in various heuristic algorithms. A contribution of the work is the introduction of new sets of topological moves. Two new algorithms for MWPSP have also been proposed. The first is an improvement heuristic, which uses a primal-dual approach, from a maximal planar subgraph of the support (primal) graph of the MWPSP instance and its dual (a cubic graph), with the application of the new proposed topological moves. This technique made the implementation and management of the proposed topological moves much simpler, compared to the version that used the primal support graph directly. The second algorithm is an exact approach (branch-and-cut), based on a MWPSP ILP model and families of restrictions (cuts) previously described in the literature. The computational results obtained with the two algorithms were satisfactory and have a higher quality than those obtained by other similar algorithms.