{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T15:20:02Z","timestamp":1770477602288,"version":"3.49.0"},"reference-count":57,"publisher":"Elsevier BV","issue":"5","license":[{"start":{"date-parts":[[2003,5,1]],"date-time":"2003-05-01T00:00:00Z","timestamp":1051747200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Parallel Computing"],"published-print":{"date-parts":[[2003,5]]},"DOI":"10.1016\/s0167-8191(03)00045-0","type":"journal-article","created":{"date-parts":[[2003,5,13]],"date-time":"2003-05-13T02:21:32Z","timestamp":1052792492000},"page":"607-629","source":"Crossref","is-referenced-by-count":37,"title":["Parallel branch and cut for capacitated vehicle routing"],"prefix":"10.1016","volume":"29","author":[{"given":"T.K.","family":"Ralphs","sequence":"first","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/S0167-8191(03)00045-0_BIB1","doi-asserted-by":"crossref","first-page":"731","DOI":"10.1002\/net.3230190702","article-title":"Set partitioning approach to vehicle routing","volume":"7","author":"Agarwal","year":"1989","journal-title":"Networks"},{"key":"10.1016\/S0167-8191(03)00045-0_BIB2","doi-asserted-by":"crossref","unstructured":"D. Applegate, R. Bixby, V. Chv\u00e1tal, W. Cook, On the solution of traveling salesman problems, Documenta Mathematica Journal der Deutschen Mathematiker-Vereinigung, International Congress of Mathematicians (1998) 645","DOI":"10.4171\/dms\/1-3\/62"},{"key":"10.1016\/S0167-8191(03)00045-0_BIB3","unstructured":"D. Applegate, R. Bixby, V. Chv\u00e1tal, W. Cook, CONCORDE TSP Solver, Available from www.keck.caam.rice.edu\/concorde.html"},{"key":"10.1016\/S0167-8191(03)00045-0_BIB4","unstructured":"J.R. Araque, L. Hall, T. Magnanti, Capacitated trees, capacitated routing and associated polyhedra, Discussion Paper 9061, CORE, Louvain La Nueve, 1990"},{"key":"10.1016\/S0167-8191(03)00045-0_BIB5","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/BF02085634","article-title":"A branch-and-cut algorithm for vehicle routing problems","volume":"50","author":"Araque","year":"1994","journal-title":"Annals of Operations Research"},{"key":"10.1016\/S0167-8191(03)00045-0_BIB6","doi-asserted-by":"crossref","first-page":"546","DOI":"10.1016\/S0377-2217(97)00290-7","article-title":"Separating capacity constraints in the CVRP using tabu search","volume":"106","author":"Augerat","year":"1998","journal-title":"European Journal of Operations Research"},{"key":"10.1016\/S0167-8191(03)00045-0_BIB7","unstructured":"P. Augerat, J.M. Belenguer, E. Benavent, A. Corber\u00e1n, D. Naddef, G. Rinaldi, Computational results with a branch and cut code for the capacitated vehicle routing problem, Research Report 949-M, Universite Joseph Fourier, Grenoble, France"},{"key":"10.1016\/S0167-8191(03)00045-0_BIB8","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1287\/mnsc.42.9.1229","article-title":"Mixed 0\u20131 programming by lift-and-project in a branch-and-cut framework","volume":"42","author":"Balas","year":"1996","journal-title":"Management Science"},{"key":"10.1016\/S0167-8191(03)00045-0_BIB9","doi-asserted-by":"crossref","first-page":"316","DOI":"10.1287\/opre.46.3.316","article-title":"Branch-and-price: column generation for huge integer programs","volume":"46","author":"Barnhart","year":"1998","journal-title":"Operations Research"},{"key":"10.1016\/S0167-8191(03)00045-0_BIB10","first-page":"221","article-title":"Building a parallel branch and bound library, in solving combinatorial optimization problems in parallel","volume":"1054","author":"Benchouche","year":"1996"},{"key":"10.1016\/S0167-8191(03)00045-0_BIB11","unstructured":"R. Bixby, W. Cook, A. Cox, E.K. Lee, Parallel mixed integer programming, Rice University Center for Research on Parallel Computation Research Monograph CRPC-TR95554, 1995"},{"key":"10.1016\/S0167-8191(03)00045-0_BIB12","unstructured":"U. Blasum, W. Hochst\u00e4ttler, Application of the branch and cut method to the vehicle routing problem, Zentrum f\u00fcr Angewandte Informatik Kol\u0308n Technical Report zpr2000-386, 2000"},{"key":"10.1016\/S0167-8191(03)00045-0_BIB13","doi-asserted-by":"crossref","unstructured":"A. de Bruin, G.A.P. Kindervater, H.W.J.M. Trienekens, Asynchronous parallel branch and bound and anomalies, Report EUR-CS-95-05, Department of Computer Science, Erasmus University, Rotterdam, 1995","DOI":"10.1007\/3-540-60321-2_29"},{"key":"10.1016\/S0167-8191(03)00045-0_BIB14","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/0377-2217(91)90337-U","article-title":"Polyhedral results for a vehicle routing problem","volume":"52","author":"Campos","year":"1991","journal-title":"European Journal of Operations Research"},{"key":"10.1016\/S0167-8191(03)00045-0_BIB15","doi-asserted-by":"crossref","unstructured":"Q. Chen, M.C. Ferris, FATCOP: a fault tolerant condor-PVM mixed integer programming solver, University of Wisconsin CS Department Technical Report 99-05, Madison, WI, 1999","DOI":"10.21236\/ADA375528"},{"key":"10.1016\/S0167-8191(03)00045-0_BIB16","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1007\/BF01589353","article-title":"Exact algorithms for solving the vehicle routing problem based on spanning trees and shortest path relaxations","volume":"20","author":"Christofides","year":"1981","journal-title":"Mathematical Programming"},{"key":"10.1016\/S0167-8191(03)00045-0_BIB17","series-title":"Linear Programming","author":"Chv\u00e1tal","year":"1983"},{"key":"10.1016\/S0167-8191(03)00045-0_BIB18","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1007\/s101070050092","article-title":"bc-opt: A branch-and-cut code for mixed integer programs","volume":"86","author":"Cordier","year":"1999","journal-title":"Mathematical Programming"},{"key":"10.1016\/S0167-8191(03)00045-0_BIB19","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/BF01580599","article-title":"Polyhedral study of the capacitated vehicle routing problem","volume":"60","author":"Cornu\u00e9jols","year":"1993","journal-title":"Mathematical Programming"},{"key":"10.1016\/S0167-8191(03)00045-0_BIB20","unstructured":"R. Correa, A. Ferreira, Parallel best-first branch and bound in discrete optimization: a framework, Center for Discrete Mathematics and Theoretical Computer Science Technical Report 95-03"},{"key":"10.1016\/S0167-8191(03)00045-0_BIB21","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1287\/mnsc.6.1.80","article-title":"The truck dispatching problem","volume":"6","author":"Dantzig","year":"1959","journal-title":"Management Science"},{"key":"10.1016\/S0167-8191(03)00045-0_BIB22","doi-asserted-by":"crossref","unstructured":"J. Eckstein, C.A. Phillips, W.E. Hart, PICO: an object-oriented framework for parallel branch and bound, RUTCOR Research Report 40-2000, Rutgers University, Piscataway, NJ, 2000","DOI":"10.2172\/771506"},{"key":"10.1016\/S0167-8191(03)00045-0_BIB23","series-title":"Computational Combinatorial Optimization","first-page":"157","article-title":"Branch-and-cut algorithms for combinatorial optimization and their implementation in ABACUS","author":"Elf","year":"2001"},{"key":"10.1016\/S0167-8191(03)00045-0_BIB24","first-page":"141","article-title":"Optimal solution of vehicle routine problems using minimum k-trees","volume":"42","author":"Fisher","year":"1988","journal-title":"Operations Research"},{"key":"10.1016\/S0167-8191(03)00045-0_BIB25","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1057\/jors.1976.63","article-title":"An integer programming approach to the vehicle scheduling problem","volume":"27","author":"Foster","year":"1976","journal-title":"Operational Research Quarterly"},{"key":"10.1016\/S0167-8191(03)00045-0_BIB26","series-title":"PVM: Parallel Virtual Machine, A User\u2019s Guide and Tutorial for Networked Parallel Computing","author":"Geist","year":"1994"},{"key":"10.1016\/S0167-8191(03)00045-0_BIB27","doi-asserted-by":"crossref","first-page":"1042","DOI":"10.1287\/opre.42.6.1042","article-title":"Parallel branch and bound algorithms: survey and synthesis","volume":"42","author":"Gendron","year":"1994","journal-title":"Operations Research"},{"key":"10.1016\/S0167-8191(03)00045-0_BIB28","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1287\/ijoc.7.4.365","article-title":"Parallel search algorithms for discrete optimization problems","volume":"7","author":"Grama","year":"1995","journal-title":"ORSA Journal on Computing"},{"key":"10.1016\/S0167-8191(03)00045-0_BIB29","doi-asserted-by":"crossref","first-page":"1155","DOI":"10.1287\/opre.32.6.1195","article-title":"A cutting plane algorithm for the linear ordering problem","volume":"32","author":"Gr\u00f6tschel","year":"1984","journal-title":"Operations Research"},{"key":"10.1016\/S0167-8191(03)00045-0_BIB30","series-title":"Geometric Algorithms and Combinatorial Optimization","author":"Gr\u00f6tschel","year":"1981"},{"key":"10.1016\/S0167-8191(03)00045-0_BIB31","doi-asserted-by":"crossref","unstructured":"D. Henrich, Initialization of parallel branch-and-bound algorithms, in: Proceedings of the Second International Workshop on Parallel Processing and Artificial Intelligence, Chamberry, France, 1993","DOI":"10.1016\/B978-0-444-81837-9.50015-4"},{"key":"10.1016\/S0167-8191(03)00045-0_BIB32","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1007\/BF02022040","article-title":"LP-based combinatorial problem solving","volume":"4","author":"Hoffman","year":"1985","journal-title":"Annals of Operations Research"},{"key":"10.1016\/S0167-8191(03)00045-0_BIB33","doi-asserted-by":"crossref","first-page":"1325","DOI":"10.1002\/1097-024X(200009)30:11<1325::AID-SPE342>3.0.CO;2-T","article-title":"The ABACUS system for branch and cut and price algorithms in integer programming and combinatorial optimization","volume":"30","author":"J\u00fcnger","year":"2000","journal-title":"Software Practice and Experience"},{"key":"10.1016\/S0167-8191(03)00045-0_BIB34","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1016\/S0167-6377(98)00013-3","article-title":"Introduction to ABACUS\u2013\u2013a branch-and-cut system","volume":"22","author":"J\u00fcnger","year":"1998","journal-title":"Operations Research Letters"},{"key":"10.1016\/S0167-8191(03)00045-0_BIB35","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/0167-6377(94)90013-2","article-title":"MINTO, a mixed INTeger optimizer","volume":"15","author":"Nemhauser","year":"1994","journal-title":"Operations Research Letters"},{"key":"10.1016\/S0167-8191(03)00045-0_BIB36","series-title":"Integer and Combinatorial Optimization","author":"Nemhauser","year":"1988"},{"key":"10.1016\/S0167-8191(03)00045-0_BIB37","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1006\/jpdc.1994.1099","article-title":"Analyzing scalability of parallel algorithms and architectures","volume":"22","author":"Kumar","year":"1994","journal-title":"Journal of Parallel and Distributed Computing"},{"key":"10.1016\/S0167-8191(03)00045-0_BIB38","doi-asserted-by":"crossref","unstructured":"L. Lad\u00e1nyi, T.K. Ralphs, M. Saltzman, Implementing scalable parallel search algorithms for data-intensive applications, in: Proceedings of the International Conference on Computational Science, vol. I, 2002, p. 592","DOI":"10.1007\/3-540-46043-8_60"},{"key":"10.1016\/S0167-8191(03)00045-0_BIB39","unstructured":"L. Lad\u00e1nyi, T.K. Ralphs, M. Saltzman, A library hierarchy for implementing scalable parallel search algorithms, Lehigh University Industrial and Systems Engineering Technical Report 01T-010, 2001"},{"key":"10.1016\/S0167-8191(03)00045-0_BIB40","series-title":"Computational Combinatorial Optimization","first-page":"223","article-title":"Branch, cut, and price: sequential and parallel","author":"Lad\u00e1nyi","year":"2001"},{"key":"10.1016\/S0167-8191(03)00045-0_BIB41","doi-asserted-by":"crossref","first-page":"497","DOI":"10.2307\/1910129","article-title":"An automatic method for solving discrete programming problems","volume":"28","author":"Land","year":"1960","journal-title":"Econometrica"},{"key":"10.1016\/S0167-8191(03)00045-0_BIB42","first-page":"271","article-title":"Comb inequalities for the vehicle routing problem","volume":"51","author":"Laporte","year":"1981","journal-title":"Methods of Operations Research"},{"key":"10.1016\/S0167-8191(03)00045-0_BIB43","doi-asserted-by":"crossref","first-page":"1050","DOI":"10.1287\/opre.33.5.1050","article-title":"Optimal routing with capacity and distance restrictions","volume":"33","author":"Laporte","year":"1985","journal-title":"Operations Research"},{"key":"10.1016\/S0167-8191(03)00045-0_BIB44","unstructured":"A.N. Letchford, R.W. Eglese, J. Lysgaard, Multi-star inequalities for the vehicle routing problem, Technical Report available at http:\/\/www.lancs.ac.uk\/staff\/letchfoa\/pubs.htm"},{"key":"10.1016\/S0167-8191(03)00045-0_BIB45","unstructured":"J. Linderoth, Topics in parallel integer optimization, Ph.D. Dissertation, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA, 1998"},{"key":"10.1016\/S0167-8191(03)00045-0_BIB46","doi-asserted-by":"crossref","first-page":"733","DOI":"10.1016\/S0167-8191(97)00016-1","article-title":"A distributed processing algorithm for solving integer programs using a cluster of workstations","volume":"23","author":"Mitra","year":"1997","journal-title":"Parallel Computing"},{"key":"10.1016\/S0167-8191(03)00045-0_BIB47","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1287\/opre.18.1.24","article-title":"Branch-and-bound methods: general formulation and properties","volume":"18","author":"Mitten","year":"1970","journal-title":"Operations Research"},{"key":"10.1016\/S0167-8191(03)00045-0_BIB48","series-title":"Vehicle Routing","article-title":"Branch and cut","author":"Naddef","year":"2000"},{"key":"10.1016\/S0167-8191(03)00045-0_BIB49","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1137\/1033004","article-title":"A branch-and-cut algorithm for the resolution of large-scale traveling salesman problems","volume":"33","author":"Padberg","year":"1991","journal-title":"SIAM Review"},{"key":"10.1016\/S0167-8191(03)00045-0_BIB50","unstructured":"T.K. Ralphs, SYMPHONY Version 3.0 User\u2019s Guide, Available from www.branchandcut.org\/SYMPHONY"},{"key":"10.1016\/S0167-8191(03)00045-0_BIB51","unstructured":"T.K. Ralphs, L. Lad\u00e1nyi, COIN\/BCP User\u2019s Guide, Available from www.coin-or.org"},{"key":"10.1016\/S0167-8191(03)00045-0_BIB52","unstructured":"T.K. Ralphs, L. Lad\u00e1nyi, M. Saltzman, Parallel branch, cut, and price for large-scale discrete optimization, to appear in Mathematical Programming, pre-print available from http:\/\/www.lehigh.edu\/~tkr2\/research\/pubs.html"},{"key":"10.1016\/S0167-8191(03)00045-0_BIB53","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1007\/s10107-002-0323-0","article-title":"On the Capacitated Vehicle Routing Problem","volume":"94","author":"Ralphs","year":"2003","journal-title":"Mathematical Programming Series B"},{"key":"10.1016\/S0167-8191(03)00045-0_BIB54","series-title":"Proceedings of the 1995 Seventh Symposium on Parallel and Distributed Processing","first-page":"392","article-title":"Generalized utility for parallel branch and bound algorithms","author":"Shinano","year":"1995"},{"key":"10.1016\/S0167-8191(03)00045-0_BIB55","unstructured":"H.W.J.M. Trienekens, A. de Bruin, Towards a taxonomy of parallel branch and bound algorithms, Report EUR-CS-92-01, Department of Computer Science, Erasmus University Rotterdam, 1992"},{"key":"10.1016\/S0167-8191(03)00045-0_BIB56","unstructured":"S. Tsch\u00f6ke, T. Polzer, Portable Parallel Branch and Bound Library User Manual, Library Version 2.0. Department of Computer Science, University of Paderborn"},{"key":"10.1016\/S0167-8191(03)00045-0_BIB57","article-title":"Solving optimization problems on computational grids","volume":"65","author":"Wright","year":"2001","journal-title":"Optima"}],"container-title":["Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0167819103000450?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0167819103000450?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2023,4,26]],"date-time":"2023-04-26T04:58:23Z","timestamp":1682485103000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0167819103000450"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,5]]},"references-count":57,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2003,5]]}},"alternative-id":["S0167819103000450"],"URL":"https:\/\/doi.org\/10.1016\/s0167-8191(03)00045-0","relation":{},"ISSN":["0167-8191"],"issn-type":[{"value":"0167-8191","type":"print"}],"subject":[],"published":{"date-parts":[[2003,5]]}}}