Exact approaches for the Minimum Subgraph Diameter Problem

Full text
Author(s):	Dadalto, Arthur Pratti ; Usberti, Fabio Luiz ; San Felice, Mario Cesar Total Authors: 3
Document type:	Journal article
Source:	Computers & Operations Research; v. 150, p. 10-pg., 2023-02-01.
Abstract
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)

FAPESP's process:	15/11937-9 - Investigation of hard problems from the algorithmic and structural stand points
Grantee:	Flávio Keidi Miyazawa
Support Opportunities:	Research Projects - Thematic Grants


FAPESP's process:	17/11382-2 - Online and Approximation Algorithms for Clustering and Network Design
Grantee:	Mário César San Felice
Support Opportunities:	Scholarships in Brazil - Post-Doctoral