{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,30]],"date-time":"2026-01-30T05:36:30Z","timestamp":1769751390365,"version":"3.49.0"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2020,1,3]],"date-time":"2020-01-03T00:00:00Z","timestamp":1578009600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,1,3]],"date-time":"2020-01-03T00:00:00Z","timestamp":1578009600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001655","name":"Deutscher Akademischer Austauschdienst","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001655","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2021,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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\u2013740, 1989; Chopra and Rao in Math Prog 64(1):209\u2013229, 1994) and the advanced flow formulation by Magnanti and Raghavan (Networks 45:61\u201379, 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.\n<\/jats:p>","DOI":"10.1007\/s10107-019-01460-6","type":"journal-article","created":{"date-parts":[[2020,1,3]],"date-time":"2020-01-03T07:03:20Z","timestamp":1578035000000},"page":"373-407","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Stronger MIP formulations for the Steiner forest problem"],"prefix":"10.1007","volume":"186","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7381-912X","authenticated-orcid":false,"given":"Daniel","family":"Schmidt","sequence":"first","affiliation":[]},{"given":"Bernd","family":"Zey","sequence":"additional","affiliation":[]},{"given":"Fran\u00e7ois","family":"Margot","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,1,3]]},"reference":[{"issue":"3","key":"1460_CR1","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1137\/S0097539792236237","volume":"24","author":"A Agrawal","year":"1995","unstructured":"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\u2013456 (1995)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"1460_CR2","doi-asserted-by":"publisher","first-page":"716","DOI":"10.1287\/opre.37.5.716","volume":"37","author":"A Balakrishnan","year":"1989","unstructured":"Balakrishnan, A., Magnanti, T.L., Wong, R.T.: A dual-ascent procedure for large-scale uncapacitated network design. Oper. Res. 37(5), 716\u2013740 (1989)","journal-title":"Oper. Res."},{"issue":"5","key":"1460_CR3","doi-asserted-by":"publisher","first-page":"21:1","DOI":"10.1145\/2027216.2027219","volume":"58","author":"M Bateni","year":"2011","unstructured":"Bateni, M., Hajiaghayi, M.T., Marx, D.: Approximation schemes for Steiner forest on planar graphs and graphs of bounded treewidth. J. ACM 58(5), 21:1\u201321:37 (2011)","journal-title":"J. ACM"},{"issue":"1","key":"1460_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2432622.2432628","volume":"60","author":"J Byrka","year":"2013","unstructured":"Byrka, J., Grandoni, F., Rothvo\u00df, T., Sanit\u00e0, L.: Steiner tree approximation via iterative randomized rounding. J. ACM 60(1), 1\u201333 (2013)","journal-title":"J. ACM"},{"issue":"4","key":"1460_CR5","doi-asserted-by":"publisher","first-page":"390","DOI":"10.1007\/PL00009180","volume":"19","author":"BV Cherkassky","year":"1997","unstructured":"Cherkassky, B.V., Goldberg, A.V.: On implementing the push-relabel method for the maximum flow problem. Algorithmica 19(4), 390\u2013410 (1997)","journal-title":"Algorithmica"},{"key":"1460_CR6","first-page":"543","volume-title":"Handbook of Graph Drawing and Visualization, Discrete Mathematics and Its Applications","author":"M Chimani","year":"2016","unstructured":"Chimani, M., Gutwenger, C., J\u00fcnger, M., Klau, G.W., Mutzel, P.: The Open Graph Drawing Framework (OGDF). In: Tamassia, R. (ed.) Handbook of Graph Drawing and Visualization, Discrete Mathematics and Its Applications, pp. 543\u2013569. Chapman and Hall, London (2016)"},{"issue":"3","key":"1460_CR7","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/j.tcs.2008.06.046","volume":"406","author":"M Chleb\u00edk","year":"2008","unstructured":"Chleb\u00edk, M., Chleb\u00edkov\u00e1, J.: The Steiner tree problem on graphs: inapproximability results. Theor. Comput. Sci. 406(3), 207\u2013214 (2008)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"1460_CR8","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1287\/ijoc.4.3.320","volume":"4","author":"S Chopra","year":"1992","unstructured":"Chopra, S., Gorres, E.R., Rao, M.R.: Solving the Steiner tree problem on a graph using branch and cut. ORSA J. Comput. 4(3), 320\u2013335 (1992)","journal-title":"ORSA J. Comput."},{"issue":"1","key":"1460_CR9","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/BF01582573","volume":"64","author":"S Chopra","year":"1994","unstructured":"Chopra, S., Rao, M.R.: The Steiner tree problem I: formulations, compositions and extension of facets. Math. Prog. 64(1), 209\u2013229 (1994)","journal-title":"Math. Prog."},{"issue":"1\u20133","key":"1460_CR10","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/BF01582574","volume":"64","author":"S Chopra","year":"1994","unstructured":"Chopra, S., Rao, M.R.: The Steiner tree problem II: properties and classes of facets. Math. Prog. 64(1\u20133), 231\u2013246 (1994)","journal-title":"Math. Prog."},{"key":"1460_CR11","unstructured":"Daneshmand, S.: Algorithmic approaches to the Steiner problem in networks. Ph.D. thesis, Universit\u00e4t Mannheim (2003)"},{"key":"1460_CR12","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1007\/3-540-36478-1_2","volume-title":"Combinatorial Optimization-Eureka, You Shrink!, no. 2570 in LNCS","author":"J Edmonds","year":"2003","unstructured":"Edmonds, J.: Submodular functions, matroids, and certain polyhedra. In: J\u00fcnger, M., Reinelt, G., Rinaldi, G. (eds.) Combinatorial Optimization-Eureka, You Shrink!, no. 2570 in LNCS, pp. 11\u201326. Springer, Berlin (2003)"},{"issue":"3","key":"1460_CR13","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/0166-218X(92)00035-K","volume":"51","author":"MX Goemans","year":"1994","unstructured":"Goemans, M.X.: Arborescence polytopes for series-parallel graphs. Discrete Appl. Math. 51(3), 277\u2013289 (1994)","journal-title":"Discrete Appl. Math."},{"issue":"1\u20133","key":"1460_CR14","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/BF01582064","volume":"63","author":"MX Goemans","year":"1994","unstructured":"Goemans, M.X.: The Steiner tree polytope and related polyhedra. Math. Prog. 63(1\u20133), 157\u2013182 (1994)","journal-title":"Math. Prog."},{"issue":"1","key":"1460_CR15","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1002\/net.3230230104","volume":"23","author":"MX Goemans","year":"1993","unstructured":"Goemans, M.X., Myung, Y.S.: A catalog of Steiner tree formulations. Networks 23(1), 19\u201328 (1993)","journal-title":"Networks"},{"issue":"2","key":"1460_CR16","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1137\/S0097539793242618","volume":"24","author":"MX Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.: A general approximation technique for constrained forest problems. SIAM J. Comput. 24(2), 296\u2013317 (1995)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"1460_CR17","doi-asserted-by":"publisher","first-page":"921","DOI":"10.1145\/48014.61051","volume":"35","author":"AV Goldberg","year":"1988","unstructured":"Goldberg, A.V., Tarjan, R.E.: A new approach to the maximum-flow problem. J. ACM 35(4), 921\u2013940 (1988)","journal-title":"J. ACM"},{"key":"1460_CR18","unstructured":"Gro\u00df, 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.\u00a094, pp. 31:1\u201331:17. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik (2018)"},{"key":"1460_CR19","doi-asserted-by":"crossref","unstructured":"Gupta, A., Kumar, A.: Greedy algorithms for steiner forest. In: Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC \u201915, pp. 871\u2013878. ACM (2015)","DOI":"10.1145\/2746539.2746590"},{"issue":"1","key":"1460_CR20","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/s004930170004","volume":"21","author":"K Jain","year":"2001","unstructured":"Jain, K.: A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica 21(1), 39\u201360 (2001)","journal-title":"Combinatorica"},{"key":"1460_CR21","unstructured":"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 \u201900, pp. 760\u2013769. SIAM (2000)"},{"issue":"3","key":"1460_CR22","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1002\/(SICI)1097-0037(199810)32:3<207::AID-NET5>3.0.CO;2-O","volume":"32","author":"T Koch","year":"1998","unstructured":"Koch, T., Martin, A.: Solving Steiner tree problems in graphs to optimality. Networks 32(3), 207\u2013232 (1998)","journal-title":"Networks"},{"issue":"5","key":"1460_CR23","doi-asserted-by":"publisher","first-page":"1319","DOI":"10.1137\/050646408","volume":"37","author":"J K\u00f6nemann","year":"2008","unstructured":"K\u00f6nemann, J., Leonardi, S., Sch\u00e4fer, G., van Zwam, S.: A group-strategyproof cost sharing mechanism for the Steiner forest game. SIAM J. Comput. 37(5), 1319\u20131341 (2008)","journal-title":"SIAM J. Comput."},{"key":"1460_CR24","unstructured":"Lucena, A.: Tight bounds for the Steiner problem in graphs. Technical report, RC for Process Systems Engineering, Imperial College, London (1993)"},{"key":"1460_CR25","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1002\/net.20046","volume":"45","author":"TL Magnanti","year":"2005","unstructured":"Magnanti, T.L., Raghavan, S.: Strong formulations for network design problems with connectivity requirements. Networks 45, 61\u201379 (2005)","journal-title":"Networks"},{"issue":"1\u20133","key":"1460_CR26","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/BF01582065","volume":"63","author":"F Margot","year":"1994","unstructured":"Margot, F., Prodon, A., Liebling, T.M.: Tree polytope on 2-trees. Math. Prog. 63(1\u20133), 183\u2013191 (1994)","journal-title":"Math. Prog."},{"key":"1460_CR27","unstructured":"Polzin, T.: Algorithms for the Steiner problem in networks. Ph.D. thesis, Universit\u00e4t des Saarlandes (2004)"},{"issue":"1\u20133","key":"1460_CR28","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1016\/S0166-218X(00)00318-8","volume":"112","author":"T Polzin","year":"2001","unstructured":"Polzin, T., Daneshmand, S.: A comparison of Steiner tree relaxations. Discrete Appl. Math. 112(1\u20133), 241\u2013261 (2001)","journal-title":"Discrete Appl. Math."},{"key":"1460_CR29","doi-asserted-by":"publisher","first-page":"70:1","DOI":"10.4230\/LIPIcs.ESA.2018.70","volume-title":"26th Annual European Symposium on Algorithms (ESA), LIPIcs","author":"DR Schmidt","year":"2018","unstructured":"Schmidt, D.R., Zey, B., Margot, F.: An exact algorithm for the Steiner forest problem. In: Azar, Y., Bast, H., Herman, G. (eds.) 26th Annual European Symposium on Algorithms (ESA), LIPIcs, vol. 112, pp. 70:1\u201370:14. Schloss Dagstuhl, Helsinki (2018). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2018.70"},{"key":"1460_CR30","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1002\/net.3230130202","volume":"13","author":"JA Wald","year":"1983","unstructured":"Wald, J.A., Colbourn, C.J.: Steiner trees, partial 2-trees and minimum IFI networks. Networks 13, 159\u2013167 (1983)","journal-title":"Networks"}],"updated-by":[{"DOI":"10.1007\/s10107-021-01648-9","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T00:00:00Z","timestamp":1620086400000}}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-019-01460-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-019-01460-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-019-01460-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,30]],"date-time":"2021-07-30T12:17:15Z","timestamp":1627647435000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-019-01460-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1,3]]},"references-count":30,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2021,3]]}},"alternative-id":["1460"],"URL":"https:\/\/doi.org\/10.1007\/s10107-019-01460-6","relation":{"correction":[{"id-type":"doi","id":"10.1007\/s10107-021-01648-9","asserted-by":"object"}]},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,1,3]]},"assertion":[{"value":"24 January 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 December 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 January 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 May 2021","order":4,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Correction","order":5,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"A Correction to this paper has been published:","order":6,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"https:\/\/doi.org\/10.1007\/s10107-021-01648-9","URL":"https:\/\/doi.org\/10.1007\/s10107-021-01648-9","order":7,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}}]}}