Stronger MIP formulations for the Steiner forest problem

• 成果类型: Article
• 署名作者: Schmidt, Daniel; Zey, Bernd; Margot, Francois
• 署名单位: University of Bonn; Dortmund University of Technology
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-019-01460-6
• 发表日期: 2021
• 页码: 373-407
• 关键词: tree problem; approximation algorithm; polytope; graphs

摘要

The Steiner forest problem asks for a minimum weight forest that spans a given number of terminal sets. We propose new cut- and flow-based integer linear programming formulations for the problem which yield stronger linear programming bounds than the two previous strongest formulations: The directed cut formulation (Balakrishnan et al. in Oper Res 37(5):716-740, 1989; Chopra and Rao in Math Prog 64(1):209-229, 1994) and the advanced flow formulation by Magnanti and Raghavan (Networks 45:61-79, 2005). We further introduce strengthening constraints and provide an example where the integrality gap of our models is 1.5. In an experimental evaluation, we show that the linear programming bounds of the new formulations are indeed strong on practical instances and that the related branch-and-cut algorithm outperforms algorithms based on the previous formulations.