.png){kind=icon}
返回
Exact approaches for the Minimum Subgraph Diameter Problem
.png){kind=icon}
PRE
AI
DOI：10.1016/j.cor.2022.106050.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
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.
Keyword:
Combinatorial optimization
Network design
Integer linear programming
Branch-and-cut
Benchmark instances
期刊
C
IF:
4.3
论文数:
6.5K
被引数:
1.8W
机构
引用论文
.png){kind=icon}
General network design: A unified view of combined location and network design problems通用网络设计: 位置和网络设计问题的统一视图
OAAI
OAAI分享收藏
分享收藏 没有更多内容
没有更多内容