Stronger path-based extended formulation for the Steiner tree problem

Bartosz Filipecki and Mathieu Van Vyve ()
Additional contact information
Mathieu Van Vyve: Université catholique de Louvain, LIDAM/CORE, Belgium

No 3129, LIDAM Reprints CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

Abstract: The Steiner tree problem (STP) is a classical NP-hard combinatorial optimization problem with applications in computational biology and network wiring. The objective of this problem is to find a minimum cost subgraph of a given undirected graph G with edge costs, that spans a subset of vertices called terminals. We present currently used linear programming formulations of the problem based on two different approaches—the bidirected cut relaxation (BCR) and the hypergraphic formulations (HYP), the former offering better computational performance, and the latter better bounds on the integrality gap. As our contribution, we propose a new hierarchy of path-based extended formulations for STP.We show that this hierarchy provides better integrality gaps on graph instances used to define the worst-case lower bounds on the integrality gap for both BCR and HYP. We prove that each consecutive level of our hierarchy is at least as strong as the previous one. Additionally, we also present numerical results showing that several difficult STP instances can be solved to integer optimality by using this hierarchy. Our approach can be adapted to variants of STP or applied to hypergraphic formulations for further potential improvement on the integrality gap bounds, in exchange for additional computational effort.

Keywords: extended formulation; flow-based formulation; integrality gap; linear programming relaxation; mixed-integer linear programming; Steiner tree (search for similar items in EconPapers)
Date: 2020-01-01
Note: In : Networks - Vol. 75, no.1, p. 3-17 (2019)
References: Add references at CitEc
Citations: View citations in EconPapers (1)

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:cor:louvrp:3129

DOI: 10.1002/net.21901

Access Statistics for this paper

More papers in LIDAM Reprints CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().