Stronger MIP formulations for the Steiner forest problem
| Autor: | Daniel R. Schmidt, Bernd Zey, François Margot |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Discrete mathematics
Linear programming General Mathematics Numerical analysis Minimum weight 0102 computer and information sciences 02 engineering and technology 01 natural sciences Flow (mathematics) 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering Steiner forest 020201 artificial intelligence & image processing Integer programming Software Mathematics |
| Zdroj: | Mathematical Programming. 186:373-407 |
| ISSN: | 1436-4646 0025-5610 |
| DOI: | 10.1007/s10107-019-01460-6 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink