{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,17]],"date-time":"2026-08-17T15:32:59Z","timestamp":1786980779468,"version":"3.56.0"},"reference-count":50,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2005,11,1]],"date-time":"2005-11-01T00:00:00Z","timestamp":1130803200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[2005,11]]},"DOI":"10.1007\/s10479-005-3977-1","type":"journal-article","created":{"date-parts":[[2005,11,26]],"date-time":"2005-11-26T07:12:53Z","timestamp":1132989173000},"page":"375-410","source":"Crossref","is-referenced-by-count":32,"title":["Non Delayed Relax-and-Cut Algorithms"],"prefix":"10.1007","volume":"140","author":[{"given":"Abilio","family":"Lucena","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"3977_CR1","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/BF01584228","volume":"21","author":"E. Balas","year":"1981","unstructured":"Balas, E. and N. Christofides. (1981). \u201cA Restricted Lagrangian Approach to the Traveling Salesman Problem.\u201d Mathematical Programming 21, 19\u201346.","journal-title":"Mathematical Programming"},{"key":"3977_CR2","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1007\/s101070050002","volume":"87","author":"F. Barahona","year":"2000","unstructured":"Barahona, F. and R. Anbil. (2000). \u201cThe Volume Algorithm: Producing Primal Solutions with the Subgradient Method.\u201d Mathematical Programming 87, 385\u2013399.","journal-title":"Mathematical Programming"},{"key":"3977_CR3","unstructured":"Barahona, F. and L. Lad\u00e1nyi. (2001). \u201cBranch and Cut Based on the Volume Algorithm: Steiner Trees in Graphs and Max-Cut.\u201d Technical report, IBM Watson Research Center."},{"key":"3977_CR4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1002\/net.3230190102","volume":"19","author":"J.E. Beasley","year":"1989","unstructured":"Beasley, J.E. (1989). \u201cAn sst-Based Algorithm for the Steiner Problem in Graphs.\u201d Networks 19, 1\u201316.","journal-title":"Networks"},{"key":"3977_CR5","volume-title":"Modern Heuristics","author":"J.E. Beasley","year":"1993","unstructured":"Beasley, J.E. (1993). \u201cLagrangean Relaxation.\u201d In Collin Reeves (ed.), Modern Heuristics, Oxford: Blackwell Scientific Press."},{"key":"3977_CR6","unstructured":"Belloni, A. and A. Lucena. (August 2000). \u201cA Relax and Cut Algorithm for the Traveling Salesman Problem.\u201d In 17th International Symposium on Mathematical Programming Atlanta."},{"key":"3977_CR7","unstructured":"Belloni, A. and A. Lucena. (2004). \u201cA Lagrangian Heuristic for the Linear Ordering Problem,\u201d In M.G.C. Resende and J.P. deSousa (eds.), Metaheuristics: Computer Decision-Making, Kluwer Academic."},{"key":"3977_CR8","unstructured":"Belloni, A. and C. Sagastiz\u00e1bal. (2004). \u201cDynamic Bundle Methods.\u201d Technical report, IMPA Preprint S'erie A 2004\/296."},{"key":"3977_CR9","unstructured":"Bonnans, J.F., J.Ch. Gilbert, C. Lemar\u00e9chal, and C. Sagastiz\u00e1bal. (1997). Optimisation Num\u00e9rique: Aspects Th\u00e9oriques et Pratiques. Springer Verlag."},{"key":"3977_CR10","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1002\/net.10058","volume":"41","author":"F. Calheiros","year":"2003","unstructured":"Calheiros, F., A. Lucena, and C.C. deSouza. (2003). \u201cOptimal Rectangular Partitions.\u201d Networks 41, 51\u201367.","journal-title":"Networks"},{"issue":"2","key":"3977_CR11","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1002\/1097-0037(200103)37:2<74::AID-NET2>3.0.CO;2-E","volume":"37","author":"L. Caccetta","year":"2001","unstructured":"Caccetta, L. and S.P. Hill. (2001). \u201cA Branch and Cut Method for the Degree-Constrained Minimum Spanning Tree Problem.\u201d Networks 37(2), 74\u201383.","journal-title":"Networks"},{"key":"3977_CR12","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/BF01582573","volume":"64","author":"S. Chopra","year":"1994","unstructured":"Chopra, S. and M.R. Rao. (1994). \u201cThe Steiner Tree Problem i: Formulations, Compositions and Extensions of Facets.\u201d Mathematical Programming 64, 209\u2013229.","journal-title":"Mathematical Programming"},{"key":"3977_CR13","unstructured":"DaCunha, A.S. and A. Lucena. (2005). \u201cLower and Upper Bounds for the Degree-Constrained Minimum Spanning Tree Problem.\u201d In INOC 2005, Lisbon."},{"key":"3977_CR14","first-page":"393","volume":"2","author":"G.B. Dantzig","year":"1954","unstructured":"Dantzig, G.B., D.R. Fulkerson, and S.M Johnson. (1954). \u201cSolution of a Large-Scale Travelling Salesman Problems.\u201d Operations Research 2, 393\u2013410.","journal-title":"Operations Research"},{"key":"3977_CR15","unstructured":"DaSilva, J.B.C. (2002). \u201cUma Heuristica Lagrangeana Para o Problema da \u00c1rvore Capacitada de Custo M\u00ednimo.\u201d Master's Thesis, Programa de Engenharia de Sistemas e Computa\u00e7\u00e3o, COPPE, Universidade Federal do Rio de Janeiro, Rio de Janeiro, Brasil."},{"issue":"5","key":"3977_CR16","doi-asserted-by":"crossref","first-page":"477","DOI":"10.1142\/S0218195900000280","volume":"10","author":"C.N. deMeneses","year":"2000","unstructured":"deMeneses, C.N. and C.C. deSouza. (2000). \u201cExact Solutions of Optimal Rectangular Partitions via Integer Programming.\u201d International Journal of Computational Geometry and Applications 10(5), 477\u2013522.","journal-title":"International Journal of Computational Geometry and Applications"},{"key":"3977_CR17","unstructured":"Duin, C.W. (1994). \u201cSteiner's Problem in Graphs: Approximation, Reduction, Variation.\u201d PhD thesis, Institute of Actuarial Science & Economics, University of Amsterdam."},{"key":"3977_CR18","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/BF01584082","volume":"1","author":"J. Edmonds","year":"1971","unstructured":"Edmonds, J. (1971). \u201cMatroids and the Greedy Algorithm.\u201d Mathematical Programming 1, 127\u2013136.","journal-title":"Mathematical Programming"},{"key":"3977_CR19","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/BF02085641","volume":"50","author":"L. Escudero","year":"1994","unstructured":"Escudero, L., M. Guignard, and K. Malik. (1994). \u201cA Lagrangian Relax and Cut Approach for the Sequential Ordering with Precedence Constraints.\u201d Annals of Operations Research 50, 219\u2013237.","journal-title":"Annals of Operations Research"},{"key":"3977_CR20","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1287\/mnsc.27.1.1","volume":"27","author":"M.L. Fisher","year":"1981","unstructured":"Fisher, M.L. (1981). \u201cThe Lagrangian Relaxation Method for Solving Integer Programming Problems.\u201d Management Science 27, 1\u201318.","journal-title":"Management Science"},{"key":"3977_CR21","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R. and D.S. Johnson. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco: W.H. Freeman and Co."},{"key":"3977_CR22","doi-asserted-by":"crossref","first-page":"1247","DOI":"10.1109\/TCOM.1985.1096250","volume":"33","author":"B. Gavish","year":"1985","unstructured":"Gavish, B. (1985). \u201cAugmented Lagrangean Based Algorithms for Centralized Network Design.\u201d IEEE Transactions on Communications 33, 1247\u20131257.","journal-title":"IEEE Transactions on Communications"},{"issue":"2","key":"3977_CR23","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/BF01582064","volume":"63","author":"M.X. Goemans","year":"1994","unstructured":"Goemans, M.X. (1994). \u201cThe Steiner Tree Polytope and Related Polyhedra.\u201d Mathematical Programming 63(2), 157\u2013182.","journal-title":"Mathematical Programming"},{"key":"3977_CR24","doi-asserted-by":"crossref","first-page":"921","DOI":"10.1145\/48014.61051","volume":"35","author":"A.V. Goldberg","year":"1988","unstructured":"Goldberg, A.V. and R.E. Tarjan. (1988) \u201cA New Approach to the Maximum Flow Problem.\u201d Journal of ACM 35, 921\u2013940.","journal-title":"Journal of ACM"},{"key":"3977_CR25","volume-title":"Recent Advances in Mathematical Programming","author":"R.E. Gomory","year":"1963","unstructured":"Gomory, R.E. (1963). \u201cAn Algorithm for Integer Solutions to Linear Programs,\u201d In R. Graves and P. Wolfe (eds.), Recent Advances in Mathematical Programming, New York: McGraw-Hill."},{"issue":"2","key":"3977_CR26","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/BF02579036","volume":"11","author":"M. Guignard","year":"2004","unstructured":"Guignard, M. (2004). \u201cLagrangean Relaxation.\u201d TOP 11(2), 151\u2013199.","journal-title":"TOP"},{"key":"3977_CR27","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1007\/BF01580223","volume":"6","author":"M. Held","year":"1974","unstructured":"Held, M., P. Wolfe, and H.P. Crowder. (1974). \u201cValidation of Subgradient Optimization.\u201d Mathematical Programming 6, 62\u201388.","journal-title":"Mathematical Programming"},{"issue":"1","key":"3977_CR28","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/S0377-2217(99)00449-X","volume":"131","author":"M. Hunting","year":"2001","unstructured":"Hunting, M., U. Faigle, and W. Kern. (2001). \u201cA lagrangian Relaxation Approach to the Edge-Weighted Clique Problem.\u201d European Journal of Operational Research 131(1), 119\u2013131.","journal-title":"European Journal of Operational Research"},{"key":"3977_CR29","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1002\/net.3230220105","volume":"22","author":"F.K. Hwang","year":"1992","unstructured":"Hwang, F.K. and D.S. Richards. (1992). \u201cSteiner Tree Problems.\u201d Networks 22, 55\u201389.","journal-title":"Networks"},{"key":"3977_CR30","unstructured":"CPLEX. (1999). ILOG, Inc. CPLEX Division."},{"key":"3977_CR31","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1090\/S0002-9939-1956-0078686-7","volume":"7","author":"J.B. Kruskal","year":"1956","unstructured":"Kruskal, J.B. (1956). \u201cOn the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem.\u201d Proceedings of the American Mathematical Society 7, 48\u201350.","journal-title":"Proceedings of the American Mathematical Society"},{"key":"3977_CR32","doi-asserted-by":"crossref","unstructured":"Letchford, A.N., G. Reinelt, and D.O. Theis. (2004). \u201cA Faster Exact Separation Algorithm for Blossom Inequalities.\u201d Lecture Notes in Computer Science 3064.","DOI":"10.1007\/978-3-540-25960-2_15"},{"key":"3977_CR33","unstructured":"Lucena, A. (1991). \u201cTight Bounds for the Steiner Problem in Graphs.\u201d In TIMS XXX - SOBRAPO XXIII Joint International Meeting, Rio de Janeiro."},{"key":"3977_CR34","first-page":"2","volume":"21","author":"A. Lucena","year":"1992","unstructured":"Lucena, A. (1992). \u201cSteiner Problem in Graphs: Lagrangean Relaxation and Cutting Planes.\u201d COAL Bulletin 21, 2\u20138.","journal-title":"COAL Bulletin"},{"key":"3977_CR35","unstructured":"Lucena, A. (1993). \u201cSteiner Problem in Graphs: Lagrangean Relaxation and Cutting Planes.\u201d In G. Gallo and F. Malucelli (eds.), Proceedings of NETFLOW93, pp. 147\u2013154."},{"key":"3977_CR36","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":"Lucena, A. and J.E. Beasley. (1998). \u201cA Branch and Cut Algorithm for the Steiner Problem in Graphs.\u201d Networks 31, 39\u201359.","journal-title":"Networks"},{"key":"3977_CR37","doi-asserted-by":"crossref","unstructured":"Maculan, N. (1987). \u201cThe Steiner Problem in Graphs.\u201d Annals of Discrete Mathematics 185\u2013222.","DOI":"10.1016\/S0304-0208(08)73236-5"},{"issue":"2","key":"3977_CR38","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1007\/BF01582065","volume":"63","author":"F. Margot","year":"1994","unstructured":"Margot, F., A. Prodon, and T.M. Liebling. (1994). \u201cTree Polyhedron on 2-Tree.\u201d Mathematical Programming 63(2), 183\u2013192.","journal-title":"Mathematical Programming"},{"key":"3977_CR39","first-page":"25","volume":"22","author":"C. Martinhon","year":"2004","unstructured":"Martinhon, C., A. Lucena, and N. Maculan. (2004). \u201cStronger $k$-Tree Relaxations for the Vehicle Routing Problem.\u201d European Journal of Operational Research 22, 25\u201345.","journal-title":"European Journal of Operational Research"},{"issue":"5","key":"3977_CR40","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1057\/jors.1992.71","volume":"43","author":"G.L. Nemhauser","year":"1992","unstructured":"Nemhauser, G.L. and G. Sigismondi. (1992). \u201cA Strong Cutting Plane Branch-and-Bound Algorithm for Node Packing.\u201d Journal of the Operational Research Society 43(5), 443\u2013457.","journal-title":"Journal of the Operational Research Society"},{"key":"3977_CR41","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1137\/1033004","volume":"33","author":"M. Padberg","year":"1991","unstructured":"Padberg, M. and G. Rinaldi. (1991). \u201cA Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems.\u201d SIAM Review 33, 60\u2013100.","journal-title":"SIAM Review"},{"key":"3977_CR42","unstructured":"Palmeira, M.M., A. Lucena, and O. Porto. (1999). \u201cA Relax and Cut Algorithm for the Quadratic Knapsack Problem.\u201d Technical report, Departamento de Administra\u00e7\u00e3o, Universidade Federal do Rio de Janeiro."},{"issue":"6","key":"3977_CR43","doi-asserted-by":"crossref","first-page":"1389","DOI":"10.1002\/j.1538-7305.1957.tb01515.x","volume":"36","author":"R.C. Prim","year":"1957","unstructured":"Prim, R.C. (1957). \u201cShortest Connection Networks and Some Generalizations.\u201d Bell System Technical Journal 36(6), 1389\u20131401.","journal-title":"Bell System Technical Journal"},{"key":"3977_CR44","unstructured":"Ralphs, T.K. and M.V. Galati. (2005). \u201cDecomposition and Dynamic Cut Generation in Integer Linear Programming.\u201d Mathematical Programming to appear."},{"key":"3977_CR45","doi-asserted-by":"crossref","unstructured":"Rayward-Smith, V.J. and A. Clare. (1986). \u201cOn Finding Steiner Vertices.\u201d Networks 16.","DOI":"10.1002\/net.3230160305"},{"issue":"3","key":"3977_CR46","doi-asserted-by":"crossref","first-page":"228","DOI":"10.1287\/ijoc.14.3.228.116","volume":"14","author":"C.C. Ribeiro","year":"2002","unstructured":"Ribeiro, C.C., E. Uchoa, and R.F. Werneck. (2002). \u201cA Hybrid Grasp with Perturbations for the Steiner Problem in Graphs.\u201d INFORMS Journal on Computing 14(3), 228\u2013246.","journal-title":"INFORMS Journal on Computing"},{"issue":"4","key":"3977_CR47","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1016\/0305-0548(85)90032-2","volume":"12","author":"M. Savelsbergh","year":"1985","unstructured":"Savelsbergh, M. and A. Volgenant. (1985). \u201cEdge Exchanges in the Degree Constrained Minimum Spanning Tree Problem.\u201d Computers and Operations Research 12(4), 341\u2013348.","journal-title":"Computers and Operations Research"},{"key":"3977_CR48","first-page":"573","volume":"6","author":"H. Takahashi","year":"1980","unstructured":"Takahashi, H. and A. Matsuyama. (1980). \u201cAn Approximate Solution for the Steiner Problem in Graphs.\u201d Mathematica Japonica 6, 573\u2013577.","journal-title":"Mathematica Japonica"},{"key":"3977_CR49","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1002\/net.3230170203","volume":"17","author":"P. Winter","year":"1987","unstructured":"Winter, P. (1987). \u201cSteiner problems in networks: A survey.\u201d Networks 17, 129\u2013167.","journal-title":"Networks"},{"key":"3977_CR50","unstructured":"Xpress-MP, release 14.05. (2004). Dash Optimization."}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-005-3977-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10479-005-3977-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-005-3977-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:59:35Z","timestamp":1559138375000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10479-005-3977-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,11]]},"references-count":50,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2005,11]]}},"alternative-id":["3977"],"URL":"https:\/\/doi.org\/10.1007\/s10479-005-3977-1","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"value":"0254-5330","type":"print"},{"value":"1572-9338","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,11]]}}}