Exact approaches for the Minimum Subgraph Diameter Problem

Autor(es)

Dadalto, Arthur Pratti ; Usberti, Fabio Luiz ; San Felice, Mario Cesar

• Tipo de documento: Artigo Científico
• Fonte: Computers & Operations Research; v. 150, p. 10-pg., 2023-02-01.

Resumo

This work addresses the Minimum Subgraph Diameter Problem (MSDP), an NP-hard problem with applications to network design. Given an undirected graph with lengths and costs on the edges, the MSDP's goal is to find a spanning subgraph with total cost limited by a given budget, such that the subgraph's diameter is minimum. We propose a Mixed-Integer Linear Programming (MILP) model for the MSDP, along with two families of valid inequalities, which form the basis of the first exact approaches for the MSDP. We present an approach to apply lazy constraints on the MILP and a heuristic to generate upper bounds from fractional solutions. We propose a comprehensive benchmark for the MSDP and conduct a thorough computational study. The results show the effectiveness of each contribution towards reducing optimality gaps and computational times. (AU)

• Processo FAPESP: 15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural
• Beneficiário: Flávio Keidi Miyazawa
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 17/11382-2 - Algoritmos Online e de Aproximação para Clusterização e Projeto de Redes
• Beneficiário: Mário César San Felice
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado