MIP Formulations for the Steiner Forest Problem
Schmidt, Daniel R. and Zey, Bernd and Margot, François
(2017)
MIP Formulations for the Steiner Forest Problem.
Technical Report
, 29 p.
Abstract
The Steiner Forest problem is among the fundamental network design problems. Finding tight linear programming bounds for the problem is the key for both fast BranchandBound algorithms and good primaldual approximations. On the theoretical side, the best known bound can be obtained from an integer program [KLSv08]. It guarantees a value that is a (2eps)approximation of the integer optimum. On the practical side, bounds from a mixed integer program by Magnanti and Raghavan [MR05] are very close to the integer optimum in computational experiments, but the size of the model limits its practical usefulness. We compare a number of known integer programming formulations for the problem and propose three new formulations. We can show that the bounds from our two new cutbased formulations for the problem are within a factor of 2 of the integer optimum. In our experiments, the formulations prove to be both tractable and provide better bounds than all other tractable formulations. In particular, the factor to the integer optimum is much better than 2 in the experiments.
Item Type:  Paper (Technical Report) 

Citations:  No citation data. 
Uncontrolled Keywords:  
Subjects: 

Divisions:  Institute of Computer Science > Computer Science Department  Prof. Dr. Juenger 
Additional Information:  Available at https://arxiv.org/abs/1709.01124 
Related URLs: 
ZAIK Number:  UNSPECIFIED 

Depositing User:  Daniel R. Schmidt 
Date Deposited:  02 Nov 2017 12:57 
Last Modified:  02 Nov 2017 12:57 
URI:  http://earchive.informatik.unikoeln.de/id/eprint/906 