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.


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: [img] PDF - Published Version Available under License Creative Commons Attribution.
Download (609kB)
Editorial actions: View Item View Item (Login required)
Deposit Information:
Depositing User: Daniel R. Schmidt
Date Deposited: 29 Aug 2018 13:23
Last Modified: 07 Dec 2018 10:45