{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T05:51:16Z","timestamp":1776059476411,"version":"3.50.1"},"reference-count":67,"publisher":"Elsevier BV","issue":"2","license":[{"start":{"date-parts":[[2000,9,1]],"date-time":"2000-09-01T00:00:00Z","timestamp":967766400000},"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":["European Journal of Operational Research"],"published-print":{"date-parts":[[2000,9]]},"DOI":"10.1016\/s0377-2217(99)00453-1","type":"journal-article","created":{"date-parts":[[2003,4,5]],"date-time":"2003-04-05T00:21:01Z","timestamp":1049502061000},"page":"222-238","source":"Crossref","is-referenced-by-count":24,"title":["Optimization engineering techniques for the exact solution of NP-hard combinatorial optimization problems"],"prefix":"10.1016","volume":"125","author":[{"given":"Paolo","family":"Toth","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0377-2217(99)00453-1_BIB1","unstructured":"D. Applegate, R.E. Bixby, V. Chv\u00e1tal, W. Cook, Finding cuts in the TSP (a preliminary report), Tech. Report 95-05, DIMACS, Rutgers University, New Brunswick, NJ, 1995"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB2","doi-asserted-by":"crossref","unstructured":"E. Balas, The asymmetric assignment problem and some new facets of the traveling salesman polytope on a directed graph, SIAM Journal on Discrete Mathematics (1989) 425\u2013451","DOI":"10.1137\/0402038"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB3","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/BF01584228","article-title":"A restricted Lagrangian approach to the traveling salesman problem","volume":"21","author":"Balas","year":"1981","journal-title":"Mathematical Programming"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB4","doi-asserted-by":"crossref","first-page":"1130","DOI":"10.1287\/opre.28.5.1130","article-title":"An algorithm for large zero\u2013one knapsack problems","volume":"28","author":"Balas","year":"1980","journal-title":"Operations Research"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB5","doi-asserted-by":"crossref","first-page":"316","DOI":"10.1287\/opre.46.3.316","article-title":"Branch-and-price: Column generation for solving huge integer programs","volume":"46","author":"Barnhart","year":"1998","journal-title":"Operations Research"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB6","series-title":"Dynamic Programming","author":"Bellman","year":"1957"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB7","doi-asserted-by":"crossref","first-page":"278","DOI":"10.1287\/opre.19.2.278","article-title":"Pathology of traveling salesman subtour elimination algorithms","volume":"19","author":"Bellmore","year":"1971","journal-title":"Operations Research"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB8","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1002\/net.3230090403","article-title":"A note on finding optimum branchings","volume":"9","author":"Camerini","year":"1979","journal-title":"Networks"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB9","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1002\/net.3230100202","article-title":"The K best spanning arborescences of a network","volume":"10","author":"Camerini","year":"1980","journal-title":"Networks"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB10","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/S0166-218X(98)00046-8","article-title":"Properties of some ILP formulations of a class of partitioning problems","volume":"87","author":"Caprara","year":"1998","journal-title":"Discrete Applied Mathematics"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB11","unstructured":"A. Caprara, M. Fischetti, Branch-and-cut algorithms, in: M. Dell'Amico, F. Maffioli, S. Martello (Eds.), Annotated Bibliographies in Combinatorial Optimization, Wiley, New York, 1997, pp. 45\u201363"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB12","unstructured":"A. Caprara, P. Toth, Lower bounds and algorithms for the 2-constraint bin packing problem, Tech. Report, DEIS OR-98-7, University of Bologna, 1998"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB13","doi-asserted-by":"crossref","first-page":"394","DOI":"10.1145\/212066.212081","article-title":"Exact solution of large-scale, asymmetric traveling salesman problems","volume":"21","author":"Carpaneto","year":"1995","journal-title":"ACM Transactions on Mathematical Software"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB14","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1145\/212066.212084","article-title":"Algorithm 750: CDT: A subroutine for the exact solution of large-scale, asymmetric traveling salesman problems","volume":"21","author":"Carpaneto","year":"1995","journal-title":"ACM Transactions on Mathematical Software"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB15","doi-asserted-by":"crossref","first-page":"736","DOI":"10.1287\/mnsc.26.7.736","article-title":"Some new branching and bounding criteria for the asymmetric travelling salesman problem","volume":"26","author":"Carpaneto","year":"1980","journal-title":"Management Science"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB16","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/0166-218X(87)90016-3","article-title":"Primal-dual algorithms for the assignment problem","volume":"18","author":"Carpaneto","year":"1987","journal-title":"Discrete Applied Mathematics"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB17","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1287\/opre.5.2.266","article-title":"Discrete variable extremum problems","volume":"5","author":"Dantzig","year":"1957","journal-title":"Operations Research"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB18","doi-asserted-by":"crossref","unstructured":"M. Dell'Amico, P. Toth, Algorithms and codes for dense assignment problems: The state of the art, Discrete Applied Mathematics, to appear","DOI":"10.1016\/S0166-218X(99)00172-9"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB19","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1007\/BF02288324","article-title":"Solving non-bipartite matching problems via shortest path techniques","volume":"13","author":"Derigs","year":"1988","journal-title":"Annals of Operations Research"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB20","doi-asserted-by":"crossref","first-page":"233","DOI":"10.6028\/jres.071B.032","article-title":"Optimum branchings","volume":"71","author":"Edmonds","year":"1967","journal-title":"Journal of Research of the National Bureau of Standards B"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB21","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1287\/mnsc.17.5.259","article-title":"The loading problem","volume":"17","author":"Eilon","year":"1971","journal-title":"Management Science"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB22","doi-asserted-by":"crossref","first-page":"272","DOI":"10.1007\/BF01580448","article-title":"Resolution of the 0\u20131 knapsack problem: Comparison of methods","volume":"8","author":"Fayard","year":"1975","journal-title":"Mathematical Programming"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB23","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF02241754","article-title":"An algorithm for the solution of the 0\u20131 knapsack problem","volume":"28","author":"Fayard","year":"1982","journal-title":"Computing"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB24","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1287\/moor.16.1.42","article-title":"Facets of the asymmetric traveling salesman polytope","volume":"16","author":"Fischetti","year":"1991","journal-title":"Mathematics of Operations Research"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB25","unstructured":"M. Fischetti, A. Lodi, P. Toth, A computational comparison of exact algorithms for the asymmetric travelling salesman problem, Tech. Report, DEIS OR-99-10, University of Bologna, 1999"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB26","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1007\/BF01585701","article-title":"An additive bounding procedure for the asymmetric travelling salesman problem","volume":"53","author":"Fischetti","year":"1992","journal-title":"Mathematical Programming"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB27","doi-asserted-by":"crossref","first-page":"426","DOI":"10.1287\/ijoc.5.4.426","article-title":"An efficient algorithm for the min-sum arborescence problem","volume":"5","author":"Fischetti","year":"1993","journal-title":"ORSA Journal of Computing"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB28","doi-asserted-by":"crossref","first-page":"1520","DOI":"10.1287\/mnsc.43.11.1520","article-title":"A polyhedral approach to the asymmetric traveling salesman problem","volume":"43","author":"Fischetti","year":"1997","journal-title":"Management Science"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB29","doi-asserted-by":"crossref","first-page":"849","DOI":"10.1287\/opre.9.6.849","article-title":"A linear programming approach to the cutting stock problem","volume":"9","author":"Gilmore","year":"1961","journal-title":"Operations Research"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB30","doi-asserted-by":"crossref","first-page":"863","DOI":"10.1287\/opre.11.6.863","article-title":"A linear programming approach to the cutting stock problem: Part II","volume":"11","author":"Gilmore","year":"1963","journal-title":"Operations Research"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB31","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1007\/BF02579273","article-title":"The ellipsoid algorithm and its consequences in combinatorial optimization","volume":"1","author":"Gr\u00f6tschel","year":"1981","journal-title":"Combinatorica"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB32","unstructured":"M. Gr\u00f6tschel, M.W. Padberg, Polyhedral theory, in: E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, D.B. Shmoys (Eds.), The Traveling Salesman Problem, Wiley, New York, 1985"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB33","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1137\/0606049","article-title":"Bithreshold graphs","volume":"6","author":"Hammer","year":"1985","journal-title":"SIAM Journal on Algebraic and Discrete Methods"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB34","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1007\/BF02085642","article-title":"Multiple-type, two-dimensional bin packing problems: Applications and algorithms","volume":"50","author":"Han","year":"1994","journal-title":"Annals of Operations Research"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB35","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1145\/321812.321823","article-title":"Computing partitions with applications to the knapsack problem","volume":"21","author":"Horowitz","year":"1974","journal-title":"Journal of ACM"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB36","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1002\/nav.3800250209","article-title":"An algorithm for a class of loading problems","volume":"25","author":"Hung","year":"1978","journal-title":"Naval Research Logistics Quarterly"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB37","doi-asserted-by":"crossref","unstructured":"M. J\u00fcnger, G. Reinelt, G. Rinaldi, The traveling salesman problem, in: M. Ball, T.L. Magnanti, C.L. Monma, G. Nemhauser (Eds.), Handbooks in Operations Research and Management Science, vol. 7, Network Models, North-Holland, Amsterdam, 1995, pp. 255\u2013330","DOI":"10.1016\/S0927-0507(05)80121-5"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB38","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/0377-2217(92)90138-Y","article-title":"The traveling salesman problem: An overview of exact and approximate algorithms","volume":"59","author":"Laporte","year":"1992","journal-title":"European Journal of Operational Research"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB39","series-title":"Combinatorial Optimization: Networks and Matroids","author":"Lawler","year":"1976"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB40","series-title":"The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization","author":"Lawler","year":"1985"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB41","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0377-2217(77)90024-8","article-title":"An upper bound for the zero\u2013one knapsack problem and a branch and bound algorithm","volume":"1","author":"Martello","year":"1977","journal-title":"European Journal of Operational Research"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB42","doi-asserted-by":"crossref","first-page":"765","DOI":"10.1287\/mnsc.30.6.765","article-title":"A mixture of dynamic programming and branch-and-bound for the subset-sum problem","volume":"30","author":"Martello","year":"1984","journal-title":"Management Science"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB43","doi-asserted-by":"crossref","first-page":"633","DOI":"10.1287\/mnsc.34.5.633","article-title":"A new algorithm for the 0\u20131 knapsack problem","volume":"34","author":"Martello","year":"1988","journal-title":"Management Science"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB44","series-title":"Knapsack Problems: Algorithms and Computer Implementations","author":"Martello","year":"1990"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB45","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/0166-218X(90)90094-S","article-title":"Lower bounds and reduction procedures for the bin packing problem","volume":"28","author":"Martello","year":"1990","journal-title":"Discrete Applied Mathematics"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB46","doi-asserted-by":"crossref","first-page":"768","DOI":"10.1287\/opre.45.5.768","article-title":"Upper bounds and algorithms for hard 0\u20131 knapsack problems","volume":"45","author":"Martello","year":"1997","journal-title":"Operations Research"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB47","unstructured":"S. Martello, P. Toth, Upper bounds and algorithms for the two-constraint knapsack problem, Tech. Report, DEIS OR-99-6, University of Bologna, 1999"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB48","doi-asserted-by":"crossref","first-page":"414","DOI":"10.1287\/mnsc.45.3.414","article-title":"Dynamic programming and strong bounds for the 0\u20131 knapsack problem","volume":"45","author":"Martello","year":"1999","journal-title":"Management Science"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB49","doi-asserted-by":"crossref","unstructured":"S. Martello, D. Pisinger, P. Toth, New trends in exact algorithms for the 0\u20131 knapsack problem, European Journal of Operational Research 123 (2) (2000) 325\u2013332","DOI":"10.1016\/S0377-2217(99)00260-X"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB50","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1287\/mnsc.23.1.27","article-title":"An efficient algorithm for the 0\u20131 knapsack problem","volume":"23","author":"Nauss","year":"1976","journal-title":"Management Science"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB51","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/BF01580850","article-title":"An efficient algorithm for the minimum capacity cut problem","volume":"47","author":"Padberg","year":"1990","journal-title":"Mathematical Programming"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB52","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1137\/1033004","article-title":"A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems","volume":"33","author":"Padberg","year":"1991","journal-title":"SIAM Review"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB53","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1007\/BF01581188","article-title":"A parallel branch-and-bound algorithm for solving large asymmetric traveling salesman problems","volume":"55","author":"Pekny","year":"1992","journal-title":"Mathematical Programming"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB54","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1016\/0377-2217(94)00013-3","article-title":"An expanding-core algorithm for the exact knapsack problem","volume":"87","author":"Pisinger","year":"1995","journal-title":"European Journal of Operational Research"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB55","doi-asserted-by":"crossref","first-page":"758","DOI":"10.1287\/opre.45.5.758","article-title":"A minimal algorithm for the 0\u20131 knapsack problem","volume":"45","author":"Pisinger","year":"1997","journal-title":"Operations Research"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB56","first-page":"277","article-title":"A hybrid algorithm for the 0\u20131 knapsack problem","volume":"49","author":"Plateau","year":"1985","journal-title":"Methods of Operations Research"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB57","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1287\/ijoc.3.4.376","article-title":"TSPLIB \u2013 a traveling salesman problem library","volume":"3","author":"Reinelt","year":"1991","journal-title":"ORSA Journal of Computing"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB58","unstructured":"T.H.C. Smith, V. Srinivasan, G.L. Thompson, Computational performance of three subtour elimination algorithms for solving asymmetric traveling salesman problems, Annals of Discrete Mathematics 1 479\u2013493"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB59","doi-asserted-by":"crossref","first-page":"627","DOI":"10.1016\/S0305-0548(96)00082-2","article-title":"BISON: A fast hybrid procedure for exactly solving the one-dimensional bin packing problem","volume":"24","author":"Scholl","year":"1997","journal-title":"Computers and Operations Research"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB60","unstructured":"P. Schwerin, G. W\u00e4scher, A new lower bound for the bin-packing problem and its integration into MTP, Tech. Report, Halle University, 1998"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB61","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/0305-0548(94)90059-0","article-title":"A branch-and-bound algorithm for the two-dimensional vector packing problem","volume":"21","author":"Spieksma","year":"1994","journal-title":"Computers and Operations Research"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB62","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1002\/net.3230070103","article-title":"Finding optimum branchings","volume":"7","author":"Tarjan","year":"1977","journal-title":"Networks"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB63","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1007\/BF02243880","article-title":"Dynamic programming algorithms for the zero\u2013one knapsack problem","volume":"25","author":"Toth","year":"1980","journal-title":"Computing"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB64","unstructured":"J.M. Valerio de Carvalho, Exact solution of bin-packing problems using column generation and branch-and-bound, Tech. Report, University of Minho, 1996"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB65","unstructured":"P.H. Vance, Branch-and-price algorithms for the one-dimensional cutting stock problem, Tech. Report, Auburn University, 1996"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB66","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/BF01300970","article-title":"Solving binary cutting stock problems by column generation and branch-and-bound","volume":"3","author":"Vance","year":"1994","journal-title":"Computational Optimization and Applications"},{"key":"10.1016\/S0377-2217(99)00453-1_BIB67","doi-asserted-by":"crossref","unstructured":"F. Vanderbeck, Computational study of a column generation algorithm for bin packing and cutting stock, Mathematical Programming 86 (1999) 565\u2013594","DOI":"10.1007\/s101070050105"}],"container-title":["European Journal of Operational Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0377221799004531?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0377221799004531?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,2,5]],"date-time":"2020-02-05T05:19:50Z","timestamp":1580879990000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0377221799004531"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,9]]},"references-count":67,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2000,9]]}},"alternative-id":["S0377221799004531"],"URL":"https:\/\/doi.org\/10.1016\/s0377-2217(99)00453-1","relation":{},"ISSN":["0377-2217"],"issn-type":[{"value":"0377-2217","type":"print"}],"subject":[],"published":{"date-parts":[[2000,9]]}}}