Common-Flow Formulations for the Diameter Constrained Spanning and Steiner Tree Problems

Luis Gouveia (), Markus Leitner () and Ivana Ljubić ()
Additional contact information
Luis Gouveia: Universidade de Lisboa, Faculdade de Ciências
Markus Leitner: Vrije Universiteit Amsterdam
Ivana Ljubić: ESSEC Business School

A chapter in Combinatorial Optimization and Applications, 2024, pp 37-58 from Springer

Abstract: Abstract We consider the diameter constrained minimum Steiner tree problem on a graph (DCStTP). Given an edge-weighted undirected graph whose set of nodes is partitioned into a set of terminal and potential Steiner nodes, the objective is to find a minimum-weight subtree that spans all terminal nodes such that the number of hops between any two terminal nodes does not exceed a given diameter D. In this work, we introduce mixed-integer linear programming models for the DCStTP based on the concept of triangles, i.e. diameter constrained Steiner trees induced by terminal subsets of size three. Starting from a formulation that models a D-hop Steiner arborescence rooted at a randomly chosen terminal node, we discuss various possibilities of realizing triangles using multi-commodity, common, or uncommon flows. We analyse the strength of these models both theoretically and empirically, and investigate how their respective Benders reformulations influence the computational performance.

Keywords: Common-flow; Diameter constraints; Spanning tree; Steiner tree; Benders’ decomposition (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:isochp:978-3-031-57603-4_3

Ordering information: This item can be ordered from
http://www.springer.com/9783031576034

DOI: 10.1007/978-3-031-57603-4_3

Access Statistics for this chapter

More chapters in International Series in Operations Research & Management Science from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().