# 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: |
PDF
- Published Version
Available under License Creative Commons Attribution.
Download (609kB) |
---|---|

Editorial actions: |
View Item (Login required) |

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 |