{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,6]],"date-time":"2026-02-06T11:24:30Z","timestamp":1770377070540,"version":"3.49.0"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2006,10,5]],"date-time":"2006-10-05T00:00:00Z","timestamp":1160006400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2008,4]]},"DOI":"10.1007\/s10107-006-0043-y","type":"journal-article","created":{"date-parts":[[2006,10,4]],"date-time":"2006-10-04T02:48:59Z","timestamp":1159930139000},"page":"443-472","source":"Crossref","is-referenced-by-count":45,"title":["Robust branch-cut-and-price for the Capacitated Minimum Spanning Tree problem over a large extended formulation"],"prefix":"10.1007","volume":"112","author":[{"given":"Eduardo","family":"Uchoa","sequence":"first","affiliation":[]},{"given":"Ricardo","family":"Fukasawa","sequence":"additional","affiliation":[]},{"given":"Jens","family":"Lysgaard","sequence":"additional","affiliation":[]},{"given":"Artur","family":"Pessoa","sequence":"additional","affiliation":[]},{"given":"Marcus Poggi","family":"de Arag\u00e3o","sequence":"additional","affiliation":[]},{"given":"Diogo","family":"Andrade","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2006,10,5]]},"reference":[{"key":"43_CR1","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1007\/s101070100234","volume":"91","author":"R. Ahuja","year":"2001","unstructured":"Ahuja R., Orlin J., Sharma D. (2001) Multi-exchange neighborhood search structures for the capacitated minimum spanning tree problem. Math. Program. 91, 71\u201397","journal-title":"Math. Program."},{"issue":"3","key":"43_CR2","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/S0167-6377(02)00236-5","volume":"31","author":"R. Ahuja","year":"2003","unstructured":"Ahuja R., Orlin J., Sharma D. (2003) A composite very large-scale neighborhood structure for the capacitated minimum spanning tree problem. Oper. Res. Lett. 31(3): 185\u2013194","journal-title":"Oper. Res. Lett."},{"key":"43_CR3","first-page":"9","volume":"1","author":"A. Amberg","year":"1996","unstructured":"Amberg A., Domschke W., Voss S. (1996) Capacitated minimum spanning trees: Algorithms using intelligent search. Comb. Optim. Theory Pract. 1, 9\u201339","journal-title":"Optim. Theory Pract."},{"key":"43_CR4","volume-title":"Capacitated trees, capacitated routing, and associated polyhedra. Technical Report OR232-90","author":"J. Araque","year":"1990","unstructured":"Araque J., Hall L., Magnanti T. (1990) Capacitated trees, capacitated routing, and associated polyhedra. Technical Report OR232-90. MIT, Operations Research Center"},{"key":"43_CR5","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1007\/s101070050002","volume":"87","author":"F. Barahona","year":"2000","unstructured":"Barahona F., Anbil R. (2000) The volume algorithm: producing primal solutions with a subgradient method. Math. Program. 87, 385\u2013399","journal-title":"Program."},{"key":"43_CR6","first-page":"318","volume":"40","author":"C. Barnhart","year":"2000","unstructured":"Barnhart C., Hane C., Vance P. (2000) Using branch-and-price-and-cut to solve origin-destination integer multicommodity flow problems. Oper. Res. 40, 318\u2013326","journal-title":"Res."},{"key":"43_CR7","doi-asserted-by":"crossref","first-page":"316","DOI":"10.1287\/opre.46.3.316","volume":"46","author":"C. Barnhart","year":"1998","unstructured":"Barnhart C., Johnson E.L., Nemhauser G.L., Savelsbergh M.W.P., Vance P.H. (1998) Branch-and-price: column generation for solving huge integer programs. Oper. Res. 46, 316\u2013329","journal-title":"Oper. Res."},{"key":"43_CR8","unstructured":"Belov G., Letchford A., Uchoa E.: A node-flow model for 1D stock cutting: Robust branch-cut-and-price. Tech. Rep. RPEP Vol.5 no.7, Universidade Federal Fluminense, Engenharia de Produ\u00e7\u00e3o, Niter\u00f3i, Brazil (2005)"},{"key":"43_CR9","unstructured":"Bergson, J.: Uma heur\u00ed stica lagrangeana para o problema da \u00e1rvore geradora capacitada de custo m\u00ed nimo. Master\u2019s thesis, Universidade Federal do Rio de Janeiro (2002)"},{"key":"43_CR10","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1007\/BF01589353","volume":"20","author":"N. Christofides","year":"1981","unstructured":"Christofides N., Mingozzi A., Toth P. (1981) Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations. Math. Program. 20, 255\u2013282","journal-title":"Math. Program."},{"key":"43_CR11","unstructured":"Duhamel, C., Gouveia, L., Moura, P., Souza, M.C.: Models and heuristics for a minimum arborescence problem. Tech. Rep. LIMOS\/RR-04-13, Institut Sup\u00e9rieur d\u2019Informatique, de Mod\u00e9lisation et de leurs Applications (2004). URL: http:\/\/www.isima.fr\/limos\/publi\/RR-04-13.pdf"},{"key":"43_CR12","doi-asserted-by":"crossref","first-page":"142","DOI":"10.1147\/sj.53.0142","volume":"5","author":"L. Esau","year":"1966","unstructured":"Esau L., Williams K. (1966) On teleprocessing system design part ii: a method for approximating the optimal network. IBM Syst. J. 5, 142\u2013147","journal-title":"IBM Syst. J."},{"key":"43_CR13","unstructured":"Felici, G., Gentile, C., Rinaldi, G.: Solving large MIP models in supply chain management by branch & cut. Tech. rep., Istituto di Analisi dei Sistemi ed Informatica del CNR, Italy (2000)"},{"key":"43_CR14","doi-asserted-by":"crossref","first-page":"491","DOI":"10.1007\/s10107-005-0644-x","volume":"106","author":"R. Fukasawa","year":"2006","unstructured":"Fukasawa R., Longo H., Lysgaard J., Poggi de Arag\u00e3o M., Reis M., Uchoa E., Werneck R.F. (2006) Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Math. Program. 106, 491\u2013511","journal-title":"Math. Program."},{"issue":"2","key":"43_CR15","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/BF02579168","volume":"6","author":"H.N. Gabow","year":"1986","unstructured":"Gabow H.N., Galil Z., Spencer T., Tarjan R.E. (1986) Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Combinatorica 6(2): 109\u2013122","journal-title":"Combinatorica"},{"key":"43_CR16","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1145\/322358.322367","volume":"30","author":"B. Gavish","year":"1983","unstructured":"Gavish B. (1983) Formulations and algorithms for the capacitated minimal directed tree problem. J. ACM 30, 118\u2013132","journal-title":"J. ACM"},{"key":"43_CR17","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1287\/opre.43.1.130","volume":"43","author":"L. Gouveia","year":"1995","unstructured":"Gouveia L. (1995) A 2n-constraint formulation for the capacitated minimal spanning tree problem. Oper. Res. 43, 130\u2013141","journal-title":"Oper. Res."},{"key":"43_CR18","doi-asserted-by":"crossref","first-page":"188","DOI":"10.1002\/net.10050","volume":"40","author":"L. Gouveia","year":"2002","unstructured":"Gouveia L., Hall L. (2002) Multistars and directed flow formulations. Networks 40, 188\u2013201","journal-title":"Networks"},{"key":"43_CR19","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/j.ejor.2003.10.021","volume":"160","author":"L. Gouveia","year":"2005","unstructured":"Gouveia L., Lopes M. (2005) The capacitated minimum spanning tree problem: On improved multistar constraints. Eur. J. Oper. Res. 160, 47\u201362","journal-title":"Eur. J. Oper. Res."},{"key":"43_CR20","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1023\/A:1018911003529","volume":"86","author":"L. Gouveia","year":"1999","unstructured":"Gouveia L., Martins P. (1999) The capacitated minimal spanning tree problem: an experiment with a hop-indexed model. Ann. Oper. Res. 86, 271\u2013294","journal-title":"Ann. Oper. Res."},{"key":"43_CR21","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1002\/(SICI)1097-0037(200001)35:1<1::AID-NET1>3.0.CO;2-L","volume":"35","author":"L. Gouveia","year":"2000","unstructured":"Gouveia L., Martins P. (2000) A hierarchy of hop-indexed models for the capacitated minimum spanning tree problem. Networks 35, 1\u201316","journal-title":"Networks"},{"key":"43_CR22","doi-asserted-by":"crossref","first-page":"2345","DOI":"10.1016\/j.cor.2004.03.011","volume":"32","author":"L. Gouveia","year":"2005","unstructured":"Gouveia L., Martins P. (2005) The capacitated minimum spanning tree problem: revisiting hop-indexed formulations. Comput. Oper. Res. 32, 2345\u20132452","journal-title":"Comput. Oper. Res."},{"key":"43_CR23","doi-asserted-by":"crossref","first-page":"1242","DOI":"10.1016\/j.cor.2004.09.013","volume":"33","author":"L. Gouveia","year":"2006","unstructured":"Gouveia L., Saldanha-da-Gama F. (2006) On the capacitated concentrator location problem: a reformulation by discretization. Comput. Oper. Res. 33, 1242\u20131258","journal-title":"Comput. Oper. Res."},{"key":"43_CR24","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1002\/net.20061","volume":"45","author":"F. Gzara","year":"2005","unstructured":"Gzara F., Goffin J.L. (2005) Exact solution of the centralized network design problem on directed graphs. Networks 45, 181\u2013192","journal-title":"Networks"},{"key":"43_CR25","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1287\/ijoc.8.3.219","volume":"8","author":"L. Hall","year":"1996","unstructured":"Hall L. (1996) Experience with a cutting plane algorithm for the capacitated spanning tree problem. INFORMS J. Comput. 8, 219\u2013234","journal-title":"INFORMS J. Comput."},{"key":"43_CR26","doi-asserted-by":"crossref","unstructured":"Hall, L., Magnanti, T.: A polyhedral intersection theorem for capacitated spanning trees. Math. Oper. Res. 17 (1992)","DOI":"10.1287\/moor.17.2.398"},{"key":"43_CR27","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1287\/trsc.33.4.391","volume":"33","author":"D. Kim","year":"1999","unstructured":"Kim D., Barnhart C., Ware K., Reinhardt G. (1999) Multimodal express package delivery: a service network design application. Transport. Sci. 33, 391\u2013407","journal-title":"Transport. Sci."},{"key":"43_CR28","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1287\/trsc.33.1.101","volume":"33","author":"N. Kohl","year":"1999","unstructured":"Kohl N., Desrosiers J., Madsen O., Solomon M., Soumis F. (1999) 2-Path cuts for the vehicle routing problem with time windows. Transport. Sci. 33, 101\u2013116","journal-title":"Transport. Sci."},{"key":"43_CR29","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1007\/s10107-005-0652-x","volume":"105","author":"A.N. Letchford","year":"2006","unstructured":"Letchford A.N., Salazar J.J. (2006) Projection results for vehicle routing. Math. Program. 105, 251\u2013274","journal-title":"Math. Program."},{"key":"43_CR30","doi-asserted-by":"crossref","first-page":"1823","DOI":"10.1016\/j.cor.2004.11.020","volume":"33","author":"H. Longo","year":"2006","unstructured":"Longo H., Poggi de Arag\u00e3o M., Uchoa E. (2006) Solving capacitated arc routing problems using a transformation to the CVRP. Comput. Oper. Res. 33, 1823\u20131837","journal-title":"Comput. Oper. Res."},{"key":"43_CR31","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1007\/s10107-003-0481-8","volume":"100","author":"J. Lysgaard","year":"2004","unstructured":"Lysgaard J., Letchford A., Eglese R. (2004) A new branch-and-cut algorithm for the capacitated vehicle routing problem. Math. Program. 100, 423\u2013445","journal-title":"Program."},{"key":"43_CR32","doi-asserted-by":"crossref","unstructured":"Malik, K., Yu, G.: A branch and bound algorithm for the capacitated minimum spanning tree problem. Networks 23 (1993)","DOI":"10.1002\/net.3230230603"},{"key":"43_CR33","doi-asserted-by":"crossref","unstructured":"Martins, P.: Enhanced second order algorithm applied to the capacitated minimum spanning tree problem. Comput. Oper. Res. (2006). (To appear)","DOI":"10.1016\/j.cor.2005.09.017"},{"key":"43_CR34","doi-asserted-by":"crossref","DOI":"10.1002\/9781118627372","volume-title":"Integer and combinatorial optimization","author":"G. Nemhauser","year":"1988","unstructured":"Nemhauser G., Wolsey L. (1988) Integer and combinatorial optimization. Wiley, New York"},{"key":"43_CR35","doi-asserted-by":"crossref","unstructured":"Pigatti, A., Poggi de Arag\u00e3o, M., Uchoa, E.: Stabilized branch-and-cut-and-price for the generalized assignment problem. In: Annals of GRACO\u201905, Electronic Notes in Discrete Mathematics, vol. 19, pp. 389\u2013395 (2005)","DOI":"10.1016\/j.endm.2005.05.052"},{"key":"43_CR36","unstructured":"Poggi de Arag\u00e3o, M., Uchoa, E.: Integer program reformulation for robust branch-and-cut-and-price. In: Annals of Mathematical Programming in Rio, pp. 56\u201361. B\u00fazios, Brazil (2003)"},{"key":"43_CR37","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1023\/A:1009629727566","volume":"5","author":"E. Rolland","year":"1999","unstructured":"Rolland E., Patterson R., Pirkul H. (1999) Memory adaptive reasoning and greedy assignment techniques for the capacitated minimum spanning tree problem. J. Heuristics 5, 159\u2013180","journal-title":"J. Heuristics"},{"key":"43_CR38","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1002\/(SICI)1097-0037(199705)29:3<161::AID-NET4>3.0.CO;2-F","volume":"29","author":"Y. Sharaiha","year":"1997","unstructured":"Sharaiha Y., Gendreau M., Laporte G., Osman I. (1997) A tabu search algorithm for the capacitated shortest spanning tree problem. Networks 29, 161\u2013171","journal-title":"Networks"},{"key":"43_CR39","doi-asserted-by":"crossref","first-page":"627","DOI":"10.1007\/978-1-4757-4137-7_30","volume-title":"Metaheuristics: Computer decision-making","author":"M. Souza","year":"2003","unstructured":"Souza M., Duhamel C., Ribeiro C. (2003) A GRASP heuristic for the capacitated minimum spanning tree problem using a memory-based local search strategy. In: Resende M., de Sousa J.(eds) Metaheuristics: Computer decision-making. Kluwer Academic Publishers, Dordrecht, pp. 627\u2013658"},{"key":"43_CR40","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/BF02098285","volume":"61","author":"P. Toth","year":"1995","unstructured":"Toth P., Vigo D. (1995) An exact algorithm for the capacitated shortest spanning arborescence. Ann. Oper. Res. 61, 121\u2013141","journal-title":"Ann. Oper. Res."},{"key":"43_CR41","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1287\/ijoc.12.2.111.11896","volume":"12","author":"J. Van den Akker","year":"2000","unstructured":"Van den Akker J., Hurkens C., Savelsbergh M. (2000) Time-indexed formulation for machine scheduling problems: column generation. INFORMS J. Comput. 12, 111\u2013124","journal-title":"INFORMS J. Comput."},{"key":"43_CR42","doi-asserted-by":"crossref","first-page":"1409","DOI":"10.1287\/mnsc.44.10.1409","volume":"44","author":"F. Vanderbeck","year":"1998","unstructured":"Vanderbeck F. (1998) Lot-sizing with start-up times. Manage. Sci. 44, 1409\u20131425","journal-title":"Manage. Sci."},{"key":"43_CR43","unstructured":"Weisstein, E.: Farey sequence. From MathWorld\u2013A Wolfram Web Resource (2006). URL: http:\/\/mathworld.wolfram.com\/FareySequence.html"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-006-0043-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-006-0043-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-006-0043-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T05:50:01Z","timestamp":1559109001000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-006-0043-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,10,5]]},"references-count":43,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,4]]}},"alternative-id":["43"],"URL":"https:\/\/doi.org\/10.1007\/s10107-006-0043-y","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,10,5]]}}}