Stronger MIP formulations for the Steiner forest problem. (English) Zbl 1459.90188
Summary: 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 [A. Balakrishnan et al., Oper. Res. 37, No. 5, 716–740 (1989; Zbl 0681.90083); S. Chopra and M. R. Rao, Math. Program. 64, No. 2 (A), 209–229 (1994; Zbl 0821.90124)] and the advanced flow formulation by T. L. Magnanti and S. Raghavan [Networks 45, No. 2, 61–79 (2005; Zbl 1067.68104)]. 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.
MSC:
| 90C27 | Combinatorial optimization |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
| 90B10 | Deterministic network models in operations research |
References:
| [1] | Agrawal, A.; Klein, P.; Ravi, R., When trees collide: an approximation algorithm for the generalized Steiner problem on networks, SIAM J. Comput., 24, 3, 440-456 (1995) · Zbl 0831.68071 · doi:10.1137/S0097539792236237 |
| [2] | Balakrishnan, A.; Magnanti, TL; Wong, RT, A dual-ascent procedure for large-scale uncapacitated network design, Oper. Res., 37, 5, 716-740 (1989) · Zbl 0681.90083 · doi:10.1287/opre.37.5.716 |
| [3] | Bateni, M.; Hajiaghayi, MT; Marx, D., Approximation schemes for Steiner forest on planar graphs and graphs of bounded treewidth, J. ACM, 58, 5, 21:1-21:37 (2011) · Zbl 1281.68233 · doi:10.1145/2027216.2027219 |
| [4] | Byrka, J.; Grandoni, F.; Rothvoß, T.; Sanità, L., Steiner tree approximation via iterative randomized rounding, J. ACM, 60, 1, 1-33 (2013) · Zbl 1281.68234 · doi:10.1145/2432622.2432628 |
| [5] | Cherkassky, BV; Goldberg, AV, On implementing the push-relabel method for the maximum flow problem, Algorithmica, 19, 4, 390-410 (1997) · Zbl 0898.68029 · doi:10.1007/PL00009180 |
| [6] | Chimani, M.; Gutwenger, C.; Jünger, M.; Klau, GW; Mutzel, P.; Tamassia, R., The Open Graph Drawing Framework (OGDF), Handbook of Graph Drawing and Visualization, Discrete Mathematics and Its Applications, 543-569 (2016), London: Chapman and Hall, London |
| [7] | Chlebík, M.; Chlebíková, J., The Steiner tree problem on graphs: inapproximability results, Theor. Comput. Sci., 406, 3, 207-214 (2008) · Zbl 1160.68023 · doi:10.1016/j.tcs.2008.06.046 |
| [8] | Chopra, S.; Gorres, ER; Rao, MR, Solving the Steiner tree problem on a graph using branch and cut, ORSA J. Comput., 4, 3, 320-335 (1992) · Zbl 0759.90091 · doi:10.1287/ijoc.4.3.320 |
| [9] | Chopra, S.; Rao, MR, The Steiner tree problem I: formulations, compositions and extension of facets, Math. Prog., 64, 1, 209-229 (1994) · Zbl 0821.90124 · doi:10.1007/BF01582573 |
| [10] | Chopra, S.; Rao, MR, The Steiner tree problem II: properties and classes of facets, Math. Prog., 64, 1-3, 231-246 (1994) · Zbl 0831.90115 · doi:10.1007/BF01582574 |
| [11] | Daneshmand, S.: Algorithmic approaches to the Steiner problem in networks. Ph.D. thesis, Universität Mannheim (2003) |
| [12] | Edmonds, J.; Jünger, M.; Reinelt, G.; Rinaldi, G., Submodular functions, matroids, and certain polyhedra, Combinatorial Optimization-Eureka, You Shrink!, no. 2570 in LNCS, 11-26 (2003), Berlin: Springer, Berlin · Zbl 1024.90054 · doi:10.1007/3-540-36478-1_2 |
| [13] | Goemans, MX, Arborescence polytopes for series-parallel graphs, Discrete Appl. Math., 51, 3, 277-289 (1994) · Zbl 0802.05040 · doi:10.1016/0166-218X(92)00035-K |
| [14] | Goemans, MX, The Steiner tree polytope and related polyhedra, Math. Prog., 63, 1-3, 157-182 (1994) · Zbl 0808.90124 · doi:10.1007/BF01582064 |
| [15] | Goemans, MX; Myung, YS, A catalog of Steiner tree formulations, Networks, 23, 1, 19-28 (1993) · Zbl 0794.90074 · doi:10.1002/net.3230230104 |
| [16] | Goemans, MX; Williamson, D., A general approximation technique for constrained forest problems, SIAM J. Comput., 24, 2, 296-317 (1995) · Zbl 0834.68055 · doi:10.1137/S0097539793242618 |
| [17] | Goldberg, AV; Tarjan, RE, A new approach to the maximum-flow problem, J. ACM, 35, 4, 921-940 (1988) · Zbl 0661.90031 · doi:10.1145/48014.61051 |
| [18] | Groß, M., Gupta, A., Kumar, A., Matuschke, J., Schmidt, D.R., Schmidt, M., Verschae, J.: A local-search algorithm for Steiner forest. In: A.R. Karlin (ed.) 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), Leibniz International Proceedings in Informatics (LIPIcs), vol. 94, pp. 31:1-31:17. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2018) · Zbl 1462.68140 |
| [19] | Gupta, A., Kumar, A.: Greedy algorithms for steiner forest. In: Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC ’15, pp. 871-878. ACM (2015) · Zbl 1321.68504 |
| [20] | Jain, K., A factor 2 approximation algorithm for the generalized Steiner network problem, Combinatorica, 21, 1, 39-60 (2001) · Zbl 1107.68533 · doi:10.1007/s004930170004 |
| [21] | Johnson, D.S., Minkoff, M., Phillips, S.: The prize collecting Steiner tree problem: theory and practice. In: Proceedings of the Symposium on Discrete Algorithms, SODA ’00, pp. 760-769. SIAM (2000) · Zbl 0956.68112 |
| [22] | Koch, T.; Martin, A., Solving Steiner tree problems in graphs to optimality, Networks, 32, 3, 207-232 (1998) · Zbl 1002.90078 · doi:10.1002/(SICI)1097-0037(199810)32:3<207::AID-NET5>3.0.CO;2-O |
| [23] | Könemann, J.; Leonardi, S.; Schäfer, G.; van Zwam, S., A group-strategyproof cost sharing mechanism for the Steiner forest game, SIAM J. Comput., 37, 5, 1319-1341 (2008) · Zbl 1225.68272 · doi:10.1137/050646408 |
| [24] | Lucena, A.: Tight bounds for the Steiner problem in graphs. Technical report, RC for Process Systems Engineering, Imperial College, London (1993) |
| [25] | Magnanti, TL; Raghavan, S., Strong formulations for network design problems with connectivity requirements, Networks, 45, 61-79 (2005) · Zbl 1067.68104 · doi:10.1002/net.20046 |
| [26] | Margot, F.; Prodon, A.; Liebling, TM, Tree polytope on 2-trees, Math. Prog., 63, 1-3, 183-191 (1994) · Zbl 0807.90118 · doi:10.1007/BF01582065 |
| [27] | Polzin, T.: Algorithms for the Steiner problem in networks. Ph.D. thesis, Universität des Saarlandes (2004) |
| [28] | Polzin, T.; Daneshmand, S., A comparison of Steiner tree relaxations, Discrete Appl. Math., 112, 1-3, 241-261 (2001) · Zbl 0984.90051 · doi:10.1016/S0166-218X(00)00318-8 |
| [29] | Schmidt, DR; Zey, B.; Margot, F.; Azar, Y.; Bast, H.; Herman, G., An exact algorithm for the Steiner forest problem, 26th Annual European Symposium on Algorithms (ESA), LIPIcs, 70:1-70:14 (2018), Helsinki: Schloss Dagstuhl, Helsinki · Zbl 1524.68242 · doi:10.4230/LIPIcs.ESA.2018.70 |
| [30] | Wald, JA; Colbourn, CJ, Steiner trees, partial 2-trees and minimum IFI networks, Networks, 13, 159-167 (1983) · Zbl 0529.68036 · doi:10.1002/net.3230130202 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
