{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T12:30:10Z","timestamp":1759667410324,"version":"3.41.0"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2003,9,1]],"date-time":"2003-09-01T00:00:00Z","timestamp":1062374400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2003,9,1]],"date-time":"2003-09-01T00:00:00Z","timestamp":1062374400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Combinatorial Optimization"],"published-print":{"date-parts":[[2003,9]]},"DOI":"10.1023\/a:1027368621279","type":"journal-article","created":{"date-parts":[[2003,11,9]],"date-time":"2003-11-09T22:46:39Z","timestamp":1068417999000},"page":"259-282","source":"Crossref","is-referenced-by-count":16,"title":["Solving Steiner Tree Problems in Graphs with Lagrangian Relaxation"],"prefix":"10.1007","volume":"7","author":[{"given":"Laura","family":"Bahiense","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Francisco","family":"Barahona","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Oscar","family":"Porto","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"5149232_CR1","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1002\/net.3230100207","volume":"10","author":"Y.P. Aneja","year":"1980","unstructured":"Y.P. Aneja, \u201cAn integer linear programming approach to the Steiner problem in graphs,\u201d Networks, vol. 10, pp. 167-178, 1980.","journal-title":"Networks"},{"key":"5149232_CR2","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/s10107-002-0357-3","volume":"94","author":"L. Bahiense","year":"2002","unstructured":"L. Bahiense, N. Maculan, and C. Sagastiz\u00b4abal, \u201cThe volume algorithm revisited: Relation with bundle methods,\u201d Mathematical Programming, vol. 94, pp. 41-69, 2002.","journal-title":"Mathematical Programming"},{"key":"5149232_CR3","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1007\/s101070050002","volume":"87","author":"F. Barahona","year":"2000","unstructured":"F. Barahona and R. Anbil, \u201cThe volume algorithm: Producing primal solutions with a subgradient method,\u201d Mathematical Programming, vol. 87, pp. 385-399, 2000.","journal-title":"Mathematical Programming"},{"key":"5149232_CR4","doi-asserted-by":"crossref","unstructured":"F. Barahona and F. Chudak. \u201cSolving large scale uncapacitated facility location problems.\u201d in P. Pardalos (Ed.), Approximation and Complexity in Numerical Optimization, Kluwer, pp. 48-62, 2000.","DOI":"10.1007\/978-1-4757-3145-3_4"},{"key":"5149232_CR5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1002\/net.3230190102","volume":"19","author":"J. Beasley","year":"1989","unstructured":"J. Beasley, \u201cAn sst-based algorithm for the Steiner problem in graphs,\u201d Networks, vol. 19, pp. 1-16, 1989.","journal-title":"Networks"},{"key":"5149232_CR6","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1002\/net.3230140112","volume":"14","author":"J. Beasley","year":"1984","unstructured":"J. Beasley, \u201cAn algorithm for the Steiner problem in graphs,\u201d Networks, vol. 14, pp. 147-159, 1984.","journal-title":"Networks"},{"key":"5149232_CR7","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1007\/BFb0120697","volume":"3","author":"P.M. Camerini","year":"1975","unstructured":"P.M. Camerini, L. Frata, and F. Maffioli, \u201cOn improving relaxation methods by modified gradient techniques,\u201d Mathematical Programming Study, vol. 3, pp. 26-34, 1975.","journal-title":"Mathematical Programming Study"},{"key":"5149232_CR8","doi-asserted-by":"crossref","first-page":"320","DOI":"10.1287\/ijoc.4.3.320","volume":"4","author":"S. Chopra","year":"1992","unstructured":"S. Chopra, E.R. Gorres, and M.R. Rao, \u201cSolving the Steiner tree problem in graphs using branch-and-cut,\u201d ORSA J. Comput, vol. 4, pp. 320-335, 1992.","journal-title":"ORSA J. Comput"},{"key":"5149232_CR9","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/BF01582573","volume":"64","author":"S. Chopra","year":"1994","unstructured":"S. Chopra and M.R. Rao, \u201cThe Steiner tree problem I: formulations, compositions and extension of facets,\u201d Mathematical Programming, vol. 64, pp. 209-229, 1994a.","journal-title":"Mathematical Programming"},{"key":"5149232_CR10","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1007\/BF01582574","volume":"64","author":"S. Chopra","year":"1994","unstructured":"S. Chopra and M.R. Rao, \u201cThe Steiner tree problem II: Properties and classes of facets,\u201d Mathematical Programming, vol. 64, pp. 231-246, 1994b.","journal-title":"Mathematical Programming"},{"key":"5149232_CR11","unstructured":"A. Claus and N. Maculan, \u201cUne nouvelle formulation du Probl\u00e8me de Steiner sur un graphe,\u201d Technical Report 280, Centre de Recerche sur les Transports, Universit\u00e9 de Montr\u00e9al, 1983."},{"key":"5149232_CR12","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1287\/opre.8.1.101","volume":"8","author":"G.B. Dantzig","year":"1960","unstructured":"G.B. Dantzig and P. Wolfe, \u201cDecomposition principle for linear programs,\u201d Operations Research, vol. 8, pp. 101-111, 1960.","journal-title":"Operations Research"},{"key":"5149232_CR13","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1002\/(SICI)1097-0037(199703)29:2<89::AID-NET3>3.0.CO;2-7","volume":"29","author":"C.W. Duin","year":"1997","unstructured":"C.W. Duin and S. Vo\u00df, \u201cEfficient path and vertex exchange in Steiner tree algorithms,\u201d Networks, vol. 29, pp. 89-105, 1997.","journal-title":"Networks"},{"key":"5149232_CR14","doi-asserted-by":"crossref","first-page":"826","DOI":"10.1137\/0132071","volume":"32","author":"M.R. Garey","year":"1977","unstructured":"M.R. Garey and D.S. Johnson, \u201cThe Rectilinear Steiner tree problem is NP-complete,\u201d SIAM Journal on Applied Mathematics, vol. 32, pp. 826-834, 1977.","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"5149232_CR15","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1002\/net.3230230104","volume":"23","author":"M.X. Goemans","year":"1993","unstructured":"M.X. Goemans and Y.S. Myung, \u201cA catalog of Steiner tree formulations.\u201d Networks, vol. 23, pp. 19-28, 1993.","journal-title":"Networks"},{"key":"5149232_CR16","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1007\/BF01580223","volume":"6","author":"M. Held","year":"1974","unstructured":"M. Held, P. Wolfe, and H.P. Crowder, \u201cValidation of subgradient optimization,\u201d Mathematical Programming, vol. 6, pp. 62-88, 1974.","journal-title":"Mathematical Programming"},{"key":"5149232_CR17","unstructured":"J.B. Hiriart-Urruty and C. Lemar\u00e9chal, Convex Analysis and Minimization Algorithms, Springer Verlag, 1991."},{"key":"5149232_CR18","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1287\/opre.46.2.247","volume":"46","author":"K. Holmberg","year":"1998","unstructured":"K. Holmberg and J. Hellstrand, \u201cSolving the uncapacitated network design problem by a Lagrangian heuristic and branch-and-bound,\u201d Operations Research, vol. 46, pp. 247-259, 1998.","journal-title":"Operations Research"},{"key":"5149232_CR19","volume-title":"Annals of Discrete Mathematics","author":"F.K. Hwang","year":"1992","unstructured":"F.K. Hwang, D.S. Richards, and P. Winter, \u201cThe Steiner tree problem,\u201d Annals of Discrete Mathematics, vol. 53. North Holland, Amsterdam, 1992."},{"key":"5149232_CR20","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1002\/net.3230220105","volume":"22","author":"F.K. Hwang","year":"1992","unstructured":"F.K. Hwang and D.S. Richards, \u201cSteiner tree problems,\u201d Networks, vol. 22, pp. 55-89, 1992.","journal-title":"Networks"},{"key":"5149232_CR21","doi-asserted-by":"crossref","unstructured":"R.M. Karp, \u201cReducibility among combinatorial problems,\u201d R.E. Miller and J.W. Thatcher (Eds.), Complexity of Computer Computations, Plenum Press, pp. 85-103, 1972.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"5149232_CR22","doi-asserted-by":"crossref","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":"T. Koch and A. Martin, \u201cSolving Steiner Tree Problems in Graphs to Optimality,\u201d Networks, vol. 32, pp. 207-232, 1998.","journal-title":"Networks"},{"key":"5149232_CR23","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1007\/BFb0120700","volume":"3","author":"C. Lemar\u00e9chal","year":"1975","unstructured":"C. Lemar\u00e9chal, \u201cAn extension of Davidon methods to nondifferentiable problems,\u201d Mathematical Programming Study, vol. 3, pp. 95-109, 1975.","journal-title":"Mathematical Programming Study"},{"key":"5149232_CR24","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-322-92106-2","volume-title":"Combinatorial Algorithms for Integrated Circuit Layout","author":"T. Lengauer","year":"1990","unstructured":"T. Lengauer, Combinatorial Algorithms for Integrated Circuit Layout, Wiley, Chichester, 1990."},{"key":"5149232_CR25","first-page":"2","volume":"21","author":"A. Lucena","year":"1992","unstructured":"A. Lucena, \u201cSteiner problem in graphs: Lagrangian relaxation and cutting-planes.\u201d COAL Bull., vol. 21, pp. 2-7, 1992.","journal-title":"COAL Bull."},{"key":"5149232_CR26","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1002\/(SICI)1097-0037(199801)31:1<39::AID-NET5>3.0.CO;2-L","volume":"31","author":"A. Lucena","year":"1998","unstructured":"A. Lucena. and J. Beasley, \u201cA branch-and-cut algorithm for the Steiner problem in graphs,\u201d Networks, vol. 31, pp. 39-59, 1998.","journal-title":"Networks"},{"key":"5149232_CR27","first-page":"185","volume":"31","author":"N. Maculan","year":"1987","unstructured":"N. Maculan, \u201cThe Steiner Problem in Graphs,\u201d Annals of Discrete Mathematics, vol. 31, pp. 185-212, 1987.","journal-title":"Annals of Discrete Mathematics"},{"key":"5149232_CR28","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1287\/trsc.18.1.1","volume":"18","author":"T.L. Magnanti","year":"1984","unstructured":"T.L. Magnanti and T. Wong, \u201cNetwork design and transportation planning: Models and algorithms.\u201d Transp. Science, vol. 18, pp. 1-55, 1984.","journal-title":"Transp. Science"},{"key":"5149232_CR29","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1002\/net.3230160305","volume":"16","author":"V.J. Rayward-Smith","year":"1986","unstructured":"V.J. Rayward-Smith and A. Clare, \u201cOn finding Steiner vertices,\u201d Networks, vol. 16, pp. 283-294, 1986.","journal-title":"Networks"},{"key":"5149232_CR30","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-82118-9","volume-title":"Minimization Methods for Non-Differentiable Functions","author":"N. Shor","year":"1985","unstructured":"N. Shor, Minimization Methods for Non-Differentiable Functions, Springer-Verlag, Berlin, 1985."},{"key":"5149232_CR31","first-page":"48","volume":"15","author":"J. Soukup","year":"1973","unstructured":"J. Soukup and W.F. Chow, \u201cSet of test problems for the minimum length connection networks,\u201d ACM\/SIGMAP Newsletters, vol. 15, pp. 48-51, 1973.","journal-title":"ACM\/SIGMAP Newsletters"},{"key":"5149232_CR32","first-page":"573","volume":"254","author":"H. Takahashi","year":"1980","unstructured":"H. Takahashi and A. Matsuyama, \u201cAn approximated solution for the Steiner tree problem in graphs,\u201d Math. Japonica, vol. 254, pp. 573-577, 1980.","journal-title":"Math. Japonica"},{"key":"5149232_CR33","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/0166-218X(92)90021-2","volume":"40","author":"S. Vo\u00df","year":"1992","unstructured":"S. Vo\u00df, \u201cSteiner's problem in graphs: Heuristic methods,\u201d Discrete Applied Mathematics, vol. 40, pp. 45-72, 1992.","journal-title":"Discrete Applied Mathematics"},{"key":"5149232_CR34","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1002\/net.3230170203","volume":"17","author":"P. Winter","year":"1987","unstructured":"P. Winter, \u201cSteiner problems in networks: A survey,\u201d Networks, vol. 17, pp. 129-167, 1987.","journal-title":"Networks"},{"key":"5149232_CR35","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1007\/BF01758765","volume":"7","author":"P. Winter","year":"1992","unstructured":"P.Winter and J.M. Smith, \u201cPath-distance heuristics for the Steiner problem in undirected networks,\u201d Algorithmica, vol. 7, pp. 309-327, 1992.","journal-title":"Algorithmica"},{"key":"5149232_CR36","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1007\/BFb0120703","volume":"3","author":"P. Wolfe","year":"1975","unstructured":"P. Wolfe, \u201cA method of conjugate subgradients for minimizing nondifferentiable functions,\u201d Mathematical Programming Study, vol. 3, pp. 145-173, 1975.","journal-title":"Mathematical Programming Study"},{"key":"5149232_CR37","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1007\/BF02612335","volume":"28","author":"R.T. Wong","year":"1984","unstructured":"R.T. Wong, \u201cA dual ascent approach for Steiner tree problems on a directed graph,\u201d Mathematical Programming, vol. 28, pp. 271-287, 1984.","journal-title":"Mathematical Programming"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1027368621279.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1023\/A:1027368621279\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1027368621279.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,30]],"date-time":"2025-06-30T11:43:45Z","timestamp":1751283825000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1023\/A:1027368621279"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,9]]},"references-count":37,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2003,9]]}},"alternative-id":["5149232"],"URL":"https:\/\/doi.org\/10.1023\/a:1027368621279","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2003,9]]}}}