An Exact Algorithm for the Steiner Forest Problem
Schmidt, Daniel R. and Zey, Bernd and Margot, François
(2018)
An Exact Algorithm for the Steiner Forest Problem.
Published In:
26th Annual European Symposium on Algorithms (ESA 2018), Leibniz International Proceedings in Informatics (LIPIcs). 112 Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik 2018, 70:1-70:14.
Abstract
The Steiner forest problem asks for a minimum weight forest that spans a given number of terminal sets. The problem has famous linear programming based 2-approximations [Agrawal et al., 1995; Goemans and Williamson, 1995; Jain, 2001] whose bottleneck is the fact that the most natural formulation of the problem as an integer linear program (ILP) has an integrality gap of 2. We propose new cut-based ILP formulations for the problem along with exact branch-and-bound based algorithms. While our new formulations cannot improve the integrality gap, we can prove that one of them yields stronger linear programming bounds than the two previous strongest formulations: The directed cut formulation [Balakrishnan et al., 1989; Chopra and Rao, 1994] and the advanced flow-based formulation by Magnanti and Raghavan [Magnanti and Raghavan, 2005]. In an experimental evaluation, we show that the linear programming bounds of the new formulations are indeed strong on practical instances and that our new branch-and-bound algorithms outperform branch-and-bound algorithms based on the previous formulations. Our formulations can be seen as a cut-based analogon to [Magnanti and Raghavan, 2005], whose existence was an open problem.
Download: |
![]() Download (609kB) |
---|---|
Editorial actions: | ![]() |
ZAIK Number: | UNSPECIFIED |
---|---|
Depositing User: | Daniel R. Schmidt |
Date Deposited: | 29 Aug 2018 13:23 |
Last Modified: | 07 Dec 2018 10:45 |
URI: | http://e-archive.informatik.uni-koeln.de/id/eprint/937 |