Busca avançada
Ano de início
Entree


Exact approaches for the Minimum Subgraph Diameter Problem

Texto completo
Autor(es):
Dadalto, Arthur Pratti ; Usberti, Fabio Luiz ; San Felice, Mario Cesar
Número total de Autores: 3
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