{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T13:07:33Z","timestamp":1773407253557,"version":"3.50.1"},"reference-count":153,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2005,10,1]],"date-time":"2005-10-01T00:00:00Z","timestamp":1128124800000},"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,10]]},"DOI":"10.1007\/s10479-005-3448-8","type":"journal-article","created":{"date-parts":[[2005,9,15]],"date-time":"2005-09-15T22:31:07Z","timestamp":1126823467000},"page":"195-227","source":"Crossref","is-referenced-by-count":61,"title":["The Multidimensional 0-1 Knapsack Problem\u2014Bounds and Computational Aspects"],"prefix":"10.1007","volume":"139","author":[{"given":"Arnaud","family":"Fr\u00e9ville","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sa\u00cfd","family":"Hanafi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"3448_CR1","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/0167-6377(89)90028-X","volume":"8","author":"R. Aboudi","year":"1989","unstructured":"Aboudi, R., A. Hallefjord, R. Helming, and K. Jornsten. (1989). \u201cA Note on the Pivot and Complement Heuristic for 0-1 Programming Problems.\u201d Operation Research Letters 8, 21\u201323.","journal-title":"Operation Research Letters"},{"key":"3448_CR2","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1287\/ijoc.6.1.82","volume":"6","author":"R. Aboudi","year":"1994","unstructured":"Aboudi, R. and K. Jornsten. (1994). \u201cTabu Search for General Zero-One Integer Programs Using the Pivot and Complement Heuristics.\u201d ORSA Journal of Computing 6, 82\u201393.","journal-title":"ORSA Journal of Computing"},{"key":"3448_CR3","unstructured":"Andonov, R., Balev S., A. Fr\u00e9ville, and N. Yanev. (2001). \u201cA Dynamic Programming Based Reduction Procedure for the Multidimensional 0-1 Knapsack Problem.\u201d Working paper, University of Valenciennes, presented at FRANCORO III, Qu\u00e9bec, Canada, may 2001."},{"key":"3448_CR4","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1007\/BF01581700","volume":"65","author":"I. Averbakh","year":"1994","unstructured":"Averbakh, I. (1994). \u201cProbabilistic Properties of the Dual Structure of the Multidimensional Knapsack Problem and Fast Statistically Efficient Algorithms.\u201d Mathematical Programming 65, 311\u2013330.","journal-title":"Mathematical Programming"},{"key":"3448_CR5","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1287\/opre.49.2.207.13535","volume":"49","author":"E. Balas","year":"2001","unstructured":"Balas, E., S. Ceria, M. Dawande, F. Margot, and G. Pataki. (2001). \u201cOCTANE: A New Heuristic for Pure 0-1 Programs.\u201d Operations Research 49, 207\u2013225.","journal-title":"Operations Research"},{"key":"3448_CR6","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1287\/mnsc.26.1.86","volume":"26","author":"E. Balas","year":"1980","unstructured":"Balas, E. and C.H. Martin. (1980). \u201cPivot and Complement\u2014A Heuristic for 0-1 Programming.\u201d Management Sciences 26, 86\u201396.","journal-title":"Management Sciences"},{"key":"3448_CR7","doi-asserted-by":"crossref","first-page":"1130","DOI":"10.1287\/opre.28.5.1130","volume":"28","author":"E. Balas","year":"1980","unstructured":"Balas, E. and E. Zemel. (1980). \u201cAn Algorithm for Large Zero-One Knapsack Problems.\u201d Operations Research 28, 1130\u20131145.","journal-title":"Operations Research"},{"key":"3448_CR8","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1016\/0141-9331(92)90003-C","volume":"16","author":"R. Battiti","year":"1992","unstructured":"Battiti, R. and G. Tecchiolli. (1992). \u201cParallel Biased Search for Combinatorial Optimization: Genetic Algorithms and Tabu Search.\u201d Microprocessors and Microsystems 16, 351\u2013367.","journal-title":"Microprocessors and Microsystems"},{"key":"3448_CR9","doi-asserted-by":"crossref","first-page":"126","DOI":"10.1287\/ijoc.6.2.126","volume":"6","author":"R. Battiti","year":"1994","unstructured":"Battiti, R. and G. Tecchiolli. (1994). \u201cThe Reactive Tabu Search.\u201d ORSA Journal on Computing 6, 126\u2013 140.","journal-title":"ORSA Journal on Computing"},{"key":"3448_CR10","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1007\/BF01719249","volume":"17","author":"R. Battiti","year":"1995","unstructured":"Battiti, R. and G. Tecchiolli. (1995). \u201cLocal Search with Memory: Benchmarking RTS.\u201d OR-Spektrum 17, 67\u201386.","journal-title":"OR-Spektrum"},{"key":"3448_CR11","doi-asserted-by":"crossref","unstructured":"Beasley, J.E. (1990). \u201cOR-Library: Distributed Test Problems by Electronic Mail.\u201d Journal of the Operational Research Society 41, 1069\u20131072 (http:\/\/mscmga.ms.ic.ac.uk\/info.html).","DOI":"10.1057\/jors.1990.166"},{"key":"3448_CR12","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1002\/1520-6750(200102)48:1<18::AID-NAV2>3.0.CO;2-7","volume":"48","author":"G.J. Beaujon","year":"2001","unstructured":"Beaujon, G.J., S.P. Martin, and C.C. McDonald. (2001). \u201cBalancing and Optimizing a Portfolio of R&D Projects.\u201d Naval Research Logistics 48, 18\u201340.","journal-title":"Naval Research Logistics"},{"key":"3448_CR13","doi-asserted-by":"crossref","unstructured":"Bixby, R.E., M. Fenelon, Z. Gu, E. Rothberg, and R. Wunderling. (2000). \u201cMIP: Theory and Practice\u2014Closing the Gap.\u201d Research paper, ILOG CPLEX Division.","DOI":"10.1007\/978-0-387-35514-6_2"},{"key":"3448_CR14","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1007\/BF01585527","volume":"7","author":"G.H. Bradley","year":"1974","unstructured":"Bradley, G.H., P.L. Hammer, and L. Wolsey. (1974). \u201cCoefficient Reduction for Inequalities in 0-1 Variables.\u201d Mathematical Programming 7, 263\u2013282.","journal-title":"Mathematical Programming"},{"key":"3448_CR15","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1287\/opre.18.2.306","volume":"18","author":"A.V. Cabot","year":"1970","unstructured":"Cabot, A.V. (1970). \u201cAn Enumeration Algorithm for Knapsack Problems.\u201d Operations Research 18, 306\u2013311.","journal-title":"Operations Research"},{"key":"3448_CR16","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1016\/0304-3975(76)90048-7","volume":"3","author":"A.K. Chandra","year":"1976","unstructured":"Chandra A.K., D.S. Hirschberg, and C.K. Wong. (1976). \u201cApproximation Algorithms for Some Generalized Knapsack Problems.\u201d Theoretical Computer Sciences 3, 293\u2013304.","journal-title":"Theoretical Computer Sciences"},{"key":"3448_CR17","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1023\/A:1009642405419","volume":"4","author":"P. Chu","year":"1998","unstructured":"Chu, P. and J. Beasley. (1998). \u201cA Genetic Algorithm for the Multidimensional Knapsack Problem.\u201d Journal of Heuristics 4, 63\u201386.","journal-title":"Journal of Heuristics"},{"key":"3448_CR18","unstructured":"CPLEX Optimization, Inc. (1994). \u201cUsing the CPLEX Callable Library and CPLEX Mixed Integer Library.\u201d Version 3.0."},{"key":"3448_CR19","first-page":"219","volume":"32","author":"Y. Crama","year":"1994","unstructured":"Crama, Y. and J. Mazzola. (1994). \u201cOn the Strength of Relaxations of Multidimensional Knapsack Problems.\u201d INFOR 32, 219\u2013225.","journal-title":"INFOR"},{"key":"3448_CR20","doi-asserted-by":"crossref","first-page":"803","DOI":"10.1287\/opre.31.5.803","volume":"31","author":"H. Crowder","year":"1983","unstructured":"Crowder, H., E. Johnson, and M. Padberg. (1983). \u201cSolving Large-Scale Zero-One Linear Programming Problems.\u201d Operations Research 31, 803\u2013834.","journal-title":"Operations Research"},{"key":"3448_CR21","unstructured":"Dammeyer, F. and S. Voss. (1991).\u201cApplication of Tabu Search Strategies for Solving Multiconstraint Zero-One Knapsack Problems.\u201d Working paper, Technische Hochschule Darmstadt, Germany."},{"key":"3448_CR22","doi-asserted-by":"crossref","unstructured":"Dammeyer, F. and S. Voss. (1993). \u201cDynamic Tabu List Management Using Reverse Elimination Method.\u201d Annals of Operations Research 31\u201346.","DOI":"10.1007\/BF02022561"},{"key":"3448_CR23","unstructured":"DASH Associates. (1994). XPRESS-MP User Manual."},{"key":"3448_CR24","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1016\/0167-6377(90)90034-3","volume":"9","author":"B.L. Dietrich","year":"1990","unstructured":"Dietrich, B.L. and L.F. Escudero. (1990). \u201cCoefficient Reduction Procedure for Knapsack-Like Constraints in 0-1 Programs with Variable Upper Bounds.\u201d Operations Research Letters 9, 9\u201314.","journal-title":"Operations Research Letters"},{"key":"3448_CR25","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/0166-218X(93)90044-O","volume":"42","author":"B.L. Dietrich","year":"1993","unstructured":"Dietrich, B.L., L.F. Escudero, and F. Chance. (1993). \u201cEffect Reformulation for 0-1 Programs: Methods and Computational Results.\u201d Discrete Applied Mathematics 42, 147\u2013175.","journal-title":"Discrete Applied Mathematics"},{"key":"3448_CR26","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1287\/moor.7.4.515","volume":"7","author":"G. Dobson","year":"1982","unstructured":"Dobson, G. (1982). \u201cWorst-Case Analysis of Greedy Heuristics for Integer Programming with Non-Negative Date.\u201d Mathematics of Operations Research 7, 515\u2013531.","journal-title":"Mathematics of Operations Research"},{"key":"3448_CR27","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02242185","volume":"40","author":"A. Drexl","year":"1988","unstructured":"Drexl, A. (1988). \u201cA Simulated Annealing Approach to the Multiconstraint Zero-One Knapsack Problem.\u201d Computing 40, 1\u20138.","journal-title":"Computing"},{"key":"3448_CR28","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/0021-9991(90)90201-B","volume":"90","author":"G. Dueck","year":"1990","unstructured":"Dueck, G. and T. Scheuer. (1990). \u201cThreshold Accepting: A General Purpose Optimization Algorithm.\u201d Journal of Computational Physics 90, 161\u2013175.","journal-title":"Journal of Computational Physics"},{"key":"3448_CR29","unstructured":"Dueck, G. and J. Wirshing. (1989). \u201cThreshold Accepting Algorithms for Multi-Constraint 0-1 Knapsack Problems.\u201d Working paper, TR 89 10 016, IBM Heidelberg Scientific Center, Germany."},{"key":"3448_CR30","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1007\/BF01581647","volume":"19","author":"H.E. Dyer","year":"1980","unstructured":"Dyer, H.E. (1980). \u201cCalculating Surrogate Constraints.\u201d Mathematical Programming 19, 255\u2013278.","journal-title":"Mathematical Programming"},{"key":"3448_CR31","doi-asserted-by":"crossref","first-page":"162","DOI":"10.1287\/moor.14.1.162","volume":"14","author":"M.E. Dyer","year":"1989","unstructured":"Dyer, M.E. and A.M. Frieze. (1989). \u201cProbabilistic Analysis of the Multidimensional Knapsack Problem.\u201d Mathematics of Operations Research 14, 162\u2013176.","journal-title":"Mathematics of Operations Research"},{"key":"3448_CR32","unstructured":"Escudero, L.F., S. Martello, and P. Toth. (1996). \u201cA Framework for Tightening 0-1 Programs Based on Extensions of Pure 0-1 KP and SS Problems.\u201d In E. Balas and J. Clausen, (eds.), Proceedings of the 4th international IPCO Conference, Berlin: Springer, pp. 110\u2013123."},{"key":"3448_CR33","unstructured":"Fayard, D. and G. Plateau. (1977). \u201cReduction Algorithm for Single and Multiple Constraints 0-1 Linear Programming Problems.\u201d In Proceedings of Congress Methods of Mathematical Programming, Zakopane, Poland."},{"key":"3448_CR34","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF02241754","volume":"28","author":"D. Fayard","year":"1982","unstructured":"Fayard, D. and G. Plateau. (1982). \u201cAlgorithm 47: An Algorithm for the Solution of the Knapsack Problem.\u201d Computing 28, 269\u2013287.","journal-title":"Computing"},{"key":"3448_CR35","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1287\/mnsc.26.1.1","volume":"26","author":"M.L. Fischer","year":"1980","unstructured":"Fischer, M.L. (1980). \u201cWorst-Case Analysis of Heuristic Algorithms.\u201d Management Sciences 26, 1\u201317.","journal-title":"Management Sciences"},{"key":"3448_CR36","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1287\/mnsc.27.1.1","volume":"27","author":"M.L. Fischer","year":"1981","unstructured":"Fischer, M.L. (1981). \u201cThe Lagrangean Relaxation Method for Solving Integer Programming Problems.\u201d Management Sciences 27, 1\u201318.","journal-title":"Management Sciences"},{"key":"3448_CR37","doi-asserted-by":"crossref","first-page":"4751","DOI":"10.1088\/0305-4470\/28\/17\/011","volume":"28","author":"J.F. Fontarani","year":"1995","unstructured":"Fontarani, J.F. (1995). \u201cA Statistical Analysis of the Knapsack Problem.\u201d Journal of Physics A\u2014Mathematical and General 28, 4751\u20134759.","journal-title":"Journal of Physics A\u2014Mathematical and General"},{"key":"3448_CR38","doi-asserted-by":"crossref","first-page":"1077","DOI":"10.1088\/0305-4470\/26\/5\/027","volume":"26","author":"J.F. Fontarani","year":"1993","unstructured":"Fontarani, J.F. and R. Meir. (1993). \u201cThe Statistical Mechanics of the Ising Perceptron.\u201d Journal of Physics A\u2014Mathematical and General 26, 1077\u20131089.","journal-title":"Journal of Physics A\u2014Mathematical and General"},{"key":"3448_CR39","unstructured":"Fr\u00e9ville, A. (2003). \u201cThe Multidimensional 0-1 Knapsack Problem: An Overview.\u201d Invited Paper to Appear in European Journal of Operational Research."},{"key":"3448_CR40","unstructured":"Fr\u00e9ville, A. and S. Hanafi (2001). \u201cBornes duales robustes pour le sac \u00e0 dos bi-dimensionnel en variables 0-1.\u201d Working paper presented at FRANCORO III, Qu\u00e9bec, Canada, May 2001."},{"key":"3448_CR41","unstructured":"Fr\u00e9ville, A. and F. Malca (2002). \u201cComparaison de m\u00e9thodes pour la r\u00e9solution du dual agr\u00e9g\u00e9 du sac \u00e0 dos multidimensionnel en variables 0-1.\u201d Rapport de recherche n\u22181\u20132002, Universit\u00e9 de Valenciennes et du Hainaut-Cambr\u00e9sis, France."},{"key":"3448_CR42","unstructured":"Fr\u00e9ville, A. et G. Plateau. (1982). \u201cM\u00e9thodes heuristiques performantes pour les programmes en variables 0-1.\u201d Working paper, ANO-91, Universit\u00e9 de Lille 1, France."},{"key":"3448_CR43","doi-asserted-by":"crossref","first-page":"206","DOI":"10.1016\/0377-2217(86)90042-1","volume":"24","author":"A. Fr\u00e9ville","year":"1986","unstructured":"Fr\u00e9ville, A. and G. Plateau. (1986). \u201cHeuristics and Reduction Methods for Multiple Constraints 0-1 Linear Programming Problems.\u201d European Journal of Operational Research, 24, 206\u2013215.","journal-title":"European Journal of Operational Research"},{"key":"3448_CR44","first-page":"251","volume":"1","author":"A. Fr\u00e9ville","year":"1990","unstructured":"Fr\u00e9ville, A. and G. Plateau. (1990). \u201cHard 0-1 Multiknapsack Test Problems for Size Reduction Methods.\u201d Investigacion Operativa 1, 251\u2013270.","journal-title":"Investigacion Operativa"},{"key":"3448_CR45","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1051\/ro\/1993270201691","volume":"27","author":"A. Fr\u00e9ville","year":"1993a","unstructured":"Fr\u00e9ville, A. and G. Plateau. (1993a). \u201cSac-\u00e0-dos Multidimensionnel en Variables 0-1: Encadrement de la somme des Variables \u00e0 l'optimum.\u201d RAIRO Operations Research 27, 169\u2013187.","journal-title":"RAIRO Operations Research"},{"key":"3448_CR46","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1016\/0377-2217(93)90197-U","volume":"68","author":"A. Fr\u00e9ville","year":"1993b","unstructured":"Fr\u00e9ville, A. and G. Plateau. (1993b). \u201cAn Exact Search for the Solution of the Surrogate Dual of the 0-1 Bidimensional Knapsack Problem.\u201d European Journal of Operational Research 68, 413\u2013421.","journal-title":"European Journal of Operational Research"},{"key":"3448_CR47","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/0166-218X(94)90209-7","volume":"49","author":"A. Fr\u00e9ville","year":"1994","unstructured":"Fr\u00e9ville, A. and G. Plateau. (1994). \u201cAn Efficient Preprocessing Procedure for the Multidimensional Knapsack Problem.\u201d Discrete Applied Mathematics 49, 189\u2013212.","journal-title":"Discrete Applied Mathematics"},{"key":"3448_CR48","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1007\/BF00247210","volume":"2","author":"A. Fr\u00e9ville","year":"1996","unstructured":"Fr\u00e9ville, A. and G. Plateau. (1996). \u201cThe 0-1 Bidimensional Knapsack Problem: Towards An Efficient High-Level Primitive Tool.\u201d Journal of Heuristics 2, 147\u2013167.","journal-title":"Journal of Heuristics"},{"key":"3448_CR49","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1016\/0377-2217(84)90053-5","volume":"15","author":"A.M. Frieze","year":"1984","unstructured":"Frieze, A.M. and M.R. Clarke. (1984). \u201cApproximate Algorithms for the m-Dimensional 0-1 Knapsack Problem: Worst-Case and Probabilistic Analyses.\u201d European Journal of Operational Research 15, 100\u2013109.","journal-title":"European Journal of Operational Research"},{"key":"3448_CR50","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/S0167-6377(99)00020-6","volume":"25","author":"V. Gabrel","year":"1999","unstructured":"Gabrel, V., A. Knippel, and M. Minoux. (1999). \u201cExact Solutions of Multicommodity Network Optimization Problems with General Step Cost Functions.\u201d Operations Research Letters 25, 15\u201323.","journal-title":"Operations Research Letters"},{"key":"3448_CR51","doi-asserted-by":"crossref","unstructured":"Gabrel, V. and M. Minoux (2002). \u201cA Scheme for Exact Separation of Extended Cover Inequalities and Application to Multidimensional Knapsack Problem.\u201d Operations Research Letters.","DOI":"10.1016\/S0167-6377(02)00124-4"},{"key":"3448_CR52","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1007\/BF02591863","volume":"31","author":"B. Gavish","year":"1985","unstructured":"Gavish, B. and H. Pirkul. (1985). \u201cEfficient Algorithms for Solving Multiconstraint Zero-One Knapsack Problems to Optimality.\u201d Mathematical Programming 31, 78\u2013105.","journal-title":"Mathematical Programming"},{"key":"3448_CR53","doi-asserted-by":"crossref","unstructured":"Gens, G.V. and E.V. Levner. (1979). \u201cComplexity and Approximation Algorithms for Combinatorial Problems: A Survey.\u201d Central economic and Mathematical Institute, Academy of Sciences of the USSR, Moscow.","DOI":"10.1007\/3-540-09526-8_26"},{"key":"3448_CR54","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1007\/BFb0120690","volume":"2","author":"A.M. Geoffrion","year":"1974","unstructured":"Geoffrion, A.M. (1974). \u201cThe Lagrangean Relaxation for Integer Programming.\u201d Mathematical Programming Study 2, 82\u2013114.","journal-title":"Mathematical Programming Study"},{"key":"3448_CR55","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1007\/BF01586944","volume":"51","author":"S. van de Gerr","year":"1991","unstructured":"van de Gerr, S., L. Stougie. (1991). \u201cOn Rates of Convergence and Asymptotic Normality in the Multiknapsack Problem.\u201d Mathematical Programming 51, 349\u2013358.","journal-title":"Mathematical Programming"},{"key":"3448_CR56","doi-asserted-by":"crossref","first-page":"1045","DOI":"10.1287\/opre.14.6.1045","volume":"14","author":"P.C. Gilmore","year":"1966","unstructured":"Gilmore P.C. and R.E. Gomory. (1966). \u201cThe Theory and Computation of Knapsack Functions.\u201d Operations Research 14, 1045\u20131075.","journal-title":"Operations Research"},{"key":"3448_CR57","doi-asserted-by":"crossref","first-page":"879","DOI":"10.1287\/opre.13.6.879","volume":"13","author":"F. Glover","year":"1965","unstructured":"Glover, F. (1965). \u201cA Multiphase-Dual Algorithm for the Zero-One Integer Programming Problem.\u201d Operations Research 13, 879\u2013919.","journal-title":"Operations Research"},{"key":"3448_CR58","doi-asserted-by":"crossref","first-page":"741","DOI":"10.1287\/opre.16.4.741","volume":"16","author":"F. Glover","year":"1968","unstructured":"Glover, F. (1968). \u201cSurrogate Constraints.\u201d Operations Research 16, 741\u2013749.","journal-title":"Operations Research"},{"key":"3448_CR59","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1287\/opre.23.3.434","volume":"23","author":"F. Glover","year":"1975","unstructured":"Glover, F. (1975). \u201cSurrogate Constraints Duality in Mathematical Programming.\u201d Operations Research 23, 434\u2013451.","journal-title":"Operations Research"},{"key":"3448_CR60","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1111\/j.1540-5915.1977.tb01074.x","volume":"8","author":"F. Glover","year":"1977","unstructured":"Glover, F. (1977). \u201cHeuristics for Integer Programming Using Surrogate Constraints.\u201d Decision Sciences 8, 156\u2013166.","journal-title":"Decision Sciences"},{"key":"3448_CR61","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1016\/0305-0548(86)90048-1","volume":"19","author":"F. Glover","year":"1986","unstructured":"Glover, F. (1986). \u201cFuture Paths for Integer Programming and Links to Artificial Intelligence.\u201d Computers and Operations Research 19, 533\u2013549.","journal-title":"Computers and Operations Research"},{"key":"3448_CR62","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1287\/ijoc.1.3.190","volume":"1","author":"F. Glover","year":"1989","unstructured":"Glover, F. (1989). \u201cTabu Search, Part 1.\u201d ORSA Journal on Computing 1, 190\u2013206.","journal-title":"ORSA Journal on Computing"},{"key":"3448_CR63","unstructured":"Glover, F. (2001). \u201cTutorial on Surrogate Constraint Approaches for Optimization in Graphs.\u201d Working paper, Hearin Center for Enterprise Science, University of Mississippi, USA."},{"key":"3448_CR64","unstructured":"Glover, F. (2003). \u201cExploiting Nested Inequalities and Surrogate Constraint.\u201d Private communication."},{"key":"3448_CR65","doi-asserted-by":"crossref","unstructured":"Glover, F. and G.A. Kochenberger. (1996). \u201cCritical Event Tabu Search for Multidimensional Knapsack Problems.\u201d In I.H. Osman and J.P. Kelly (eds.), Meta-heuristics: Theory and Applications. Kluwer Academic Publishers, pp. 407\u2013427.","DOI":"10.1007\/978-1-4613-1361-8_25"},{"key":"3448_CR66","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1023\/A:1008621204567","volume":"8","author":"F. Glover","year":"1997","unstructured":"Glover, F., Sherali H, and Y. Lee. (1997). \u201cGenerating Cuts from Surrogate Constraint Analysis for Zero-One and Multiple Choice Programming.\u201d Computational Optimization and Applications 8, 154\u2013 184.","journal-title":"Computational Optimization and Applications"},{"key":"3448_CR67","unstructured":"Gotlieb, J. (1999). \u201cOn the Effectivity of Evolutionary Algorithms for Multidimensional Knapsack Problem.\u201d Proceedings of Artificial Evolution (forth coming)."},{"key":"3448_CR68","unstructured":"Green, C.J. (1967). \u201cTwo Algorithms for Solving Independent Multidimensional Knapsack Problems.\u201d Management Sciences Report n\u2218 110, Carnegie institute of Technology, Graduate School of Industrial Administration, Pittsburgh, USA."},{"key":"3448_CR69","doi-asserted-by":"crossref","first-page":"924","DOI":"10.1287\/opre.18.5.924","volume":"18","author":"H. Greenberg","year":"1970","unstructured":"Greenberg, H. and W. Pierskalla. (1970). \u201cSurrogate Mathematical Programs.\u201d Operations Research 18, 924\u2013939.","journal-title":"Operations Research"},{"key":"3448_CR70","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/BF02592954","volume":"39","author":"M. Guignard","year":"1987a","unstructured":"Guignard, M. and S. Kim. (1987a). \u201cLagrangean Decomposition: A Model Yielding Stronger Lagrangean Bounds.\u201d Mathematical Programming Study 39, 215\u2013228.","journal-title":"Mathematical Programming Study"},{"key":"3448_CR71","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1051\/ro\/1987210403071","volume":"21","author":"M. Guignard","year":"1987b","unstructured":"Guignard, M. and S. Kim. (1987b). \u201cLagrangean Decomposition for Integer Programming: Theory and Applications.\u201d RAIRO 21, 307\u2013323.","journal-title":"RAIRO"},{"key":"3448_CR72","unstructured":"Guignard, M. and K. Spielberg. (1969). \u201cSearch Techniques with Adaptive Features for Certain Integer and Mixed Integer Programming Problems.\u201d Proceedings Information Processing 1968, Edinburgh, North Holland Publishing Company, pp. 238\u2013244."},{"key":"3448_CR73","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1287\/opre.29.1.49","volume":"29","author":"M. Guignard","year":"1981","unstructured":"Guignard, M. and K. Spielberg. (1981), \u201cLogical Reduction Methods in Zero-One Programming (Minimal Preferred Variables).\u201d Operations Research 29, 49\u201374.","journal-title":"Operations Research"},{"key":"3448_CR74","first-page":"68","volume":"13","author":"P. Hammer","year":"1975","unstructured":"Hammer, P., M. Padberg, and U. Peled. (1975). \u201cConstraint Pairing in Integer Programming.\u201d INFOR 13, 68\u201381.","journal-title":"INFOR"},{"key":"3448_CR75","unstructured":"Hanafi, S. (1993). \u201cContribution \u00e0 la R\u00e9solution de Probl\u00e8mes Duaux de Grande Taille en Optimisation Combinatoire.\u201d PhD thesis, University of Valenciennes, France."},{"key":"3448_CR76","doi-asserted-by":"crossref","first-page":"659","DOI":"10.1016\/S0377-2217(97)00296-8","volume":"106","author":"S. Hanafi","year":"1998","unstructured":"Hanafi, S. and A. Fr\u00e9ville. (1998). \u201cAn Efficient Tabu Search Approach for the 0-1 Multidimensional Knapsack Problem.\u201d European Journal of Operational Research 106, 659\u2013675.","journal-title":"European Journal of Operational Research"},{"key":"3448_CR77","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1051\/ro:2001113","volume":"35","author":"S. Hanafi","year":"2001","unstructured":"Hanafi, S. and A. Fr\u00e9ville (2001). \u201cExtension of Reverse Elimination Method Through a Dynamic Management of the Tabu List.\u201d RAIRO Operations Research 35, 251\u2013267.","journal-title":"RAIRO Operations Research"},{"key":"3448_CR78","doi-asserted-by":"crossref","unstructured":"Haul, C. and S. Voss. (1998). \u201cUsing Surrogate Constraints in Genetic Algorithms for Solving Multidimensional Knapsack Problems.\u201d in D.L. Woodruff (ed.), Advances in Computational and Stochastic Optimization, Logic Programming, and Heuristic Search, Kluwer Academic Publishers, pp. 235\u2013251.","DOI":"10.1007\/978-1-4757-2807-1_9"},{"key":"3448_CR79","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1287\/mnsc.46.2.302.11930","volume":"46","author":"R. Hill","year":"2000","unstructured":"Hill, R. and C. Reilly (2000). \u201cThe Effects of Coefficient Correlation Structure in Two-Dimensional Knapsack Problems on Solution Procedure Performance.\u201d Management Sciences 46, 302\u2013317.","journal-title":"Management Sciences"},{"key":"3448_CR80","doi-asserted-by":"crossref","first-page":"600","DOI":"10.1287\/opre.17.4.600","volume":"17","author":"F.S. Hillier","year":"1969","unstructured":"Hillier, F.S. (1969). \u201cEfficient Heuristic Procedures for Integer Linear Programming with an Interior.\u201d Operations Research 17, 600\u2013637.","journal-title":"Operations Research"},{"key":"3448_CR81","unstructured":"Ibaraki, T. (1987). \u201cEnumerative Approaches to Combinatorial Optimization\u2014Part II.\u201d Annals of Operations Research vol. 11."},{"key":"3448_CR82","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1145\/321906.321909","volume":"22","author":"O.H. Ibarra","year":"1975","unstructured":"Ibarra, O.H. and C.E. Kim. (1975). \u201cFast Approximation Algorithms for the Knapsack and Sum of Subset Problems.\u201d Journal of Association for Computing Machinery 22, 463\u2013468.","journal-title":"Journal of Association for Computing Machinery"},{"key":"3448_CR83","unstructured":"[97] IBM Corporation. (1990). Optimization subroutine library, Guide and Reference."},{"key":"3448_CR84","unstructured":"Ibaraki, T. and S. Isaka. (1983). \u201cDouble Relaxation Dynamic Programming Methods for the Multi-Dimensional Knapsack Problem.\u201d Master Thesis, Department of Applied Mathematics and Physics, Kyoto University, Japan."},{"key":"3448_CR85","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1287\/ijoc.12.1.2.11900","volume":"12","author":"E.J. Johnson","year":"2000","unstructured":"Johnson, E.J., G.L. Nemhauser, and M.W.P. Savelsbergh (2000). \u201cProgress in Linear Programming-Based Algorithms for Integer Programming: An Exposition.\u201d INFORMS Journal on Computing 12, 2\u201323.","journal-title":"INFORMS Journal on Computing"},{"key":"3448_CR86","doi-asserted-by":"crossref","first-page":"320","DOI":"10.1007\/BF01588253","volume":"17","author":"M.H. Karwan","year":"1979","unstructured":"Karwan, M.H. and R.L. Rardin. (1979). \u201cSome Relationships Between Lagrangian and Surrogate Duality in Integer Programming.\u201d Mathematical Programming 17, 320\u2013334.","journal-title":"Mathematical Programming"},{"key":"3448_CR87","doi-asserted-by":"crossref","first-page":"1251","DOI":"10.1287\/opre.28.5.1251","volume":"28","author":"M.H. Karwan","year":"1980","unstructured":"Karwan, M.H. and R.L. Rardin. (1980). \u201cSearchability of the Composite and Multiple Surrogate Dual Functions.\u201d Operations Research 28, 1251\u20131257.","journal-title":"Operations Research"},{"key":"3448_CR88","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1287\/opre.32.1.52","volume":"32","author":"M.H. Karwan","year":"1984","unstructured":"Karwan, M.H. and R.L. Rardin. (1984). \u201cSurrogate Dual Multiplier Search Procedures in Integer Programming.\u201d Operations Research 32, 52\u201369.","journal-title":"Operations Research"},{"key":"3448_CR89","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1002\/1520-6750(198706)34:3<431::AID-NAV3220340309>3.0.CO;2-P","volume":"34","author":"M.H. Karwan","year":"1987","unstructured":"Karwan, M.H. R.L. Rardin, and S. Sarin. (1987). \u201cA New Surrogate Dual Multiplier Search Procedure.\u201d Naval Research Logistics 34, 431\u2013450.","journal-title":"Naval Research Logistics"},{"key":"3448_CR90","doi-asserted-by":"crossref","unstructured":"Khuri, S., T. Back, and J. Heitkotter. (1994). \u201cThe Zero\/One Multiple Knapsack Problem and Genetic Algorithms.\u201d Proceedings of the 1994 ACM Symposium on Applied Computing (SAC'99), ACM Press, pp. 188\u2013193.","DOI":"10.1145\/326619.326694"},{"key":"3448_CR91","doi-asserted-by":"crossref","first-page":"1374","DOI":"10.1287\/opre.19.6.1374","volume":"19","author":"F. Kianfar","year":"1971","unstructured":"Kianfar, F. (1971). \u201cStronger Inequalities for 0-1 Integer Programming Using Knapsack Constraints.\u201d Operations Research 19, 1374\u20131392.","journal-title":"Operations Research"},{"key":"3448_CR92","unstructured":"Kleinmuntz, D.N. and C.E. Kleinmuntz. (2001). \u201cMultiobjective Capital Budgeting in Not-for-Profit Hospitals and Healthcare Systems.\u201d Working paper, University of Illinois, Urbana-Champaign, USA, October 2001."},{"key":"3448_CR93","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1111\/j.1540-5915.1974.tb00593.x","volume":"5","author":"G. Kochenberger","year":"1974","unstructured":"Kochenberger, G., G. McCarl, and F. Wyman. (1974). \u201cA Heuristic for General Integer Programming.\u201d Decision Sciences 5, 36\u201344.","journal-title":"Decision Sciences"},{"key":"3448_CR94","unstructured":"Korte, B. and R. Schnader. (1980). \u201cOn the Existence of Fast Approximate Schemes.\u201d In O.L. Mangasarian, R.R. Meyer, S.M. Robinson (eds.), Nonlinear Programming Academic Press, pp. 415\u2013437."},{"key":"3448_CR95","doi-asserted-by":"crossref","first-page":"L645","DOI":"10.1088\/0305-4470\/27\/18\/001","volume":"27","author":"E. Korutcheva","year":"1994","unstructured":"Korutcheva, E., M. Opper, and B. Lopez. (1994). \u201cStatistical Mechanics of the Knapsack Problem.\u201d Journal of Physics A: Mathematics and General 27, L645\u2013L650.","journal-title":"Journal of Physics A: Mathematics and General"},{"key":"3448_CR96","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/BF00246001","volume":"7","author":"W. Kwak","year":"1996","unstructured":"Kwak, W., Y. Shi, H. Lee, and C.F. Lee. (1996). \u201cCapital Budgeting with Multiple Criteria and Multiple Decision Makers.\u201d Review of Quantitative Finance and Accounting 7, 97\u2013112.","journal-title":"Review of Quantitative Finance and Accounting"},{"key":"3448_CR97","doi-asserted-by":"crossref","first-page":"176","DOI":"10.1016\/0377-2217(93)E0174-V","volume":"82","author":"M. Laguna","year":"1995","unstructured":"Laguna, M., J.P. Kelly, J.L. Gonzalez Velarde, and F. Glover. (1995). \u201cTabu Search for the Multilevel Generalized Assignment Problem.\u201d European Journal of Operational Research 82, 176\u2013189.","journal-title":"European Journal of Operational Research"},{"key":"3448_CR98","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1287\/moor.4.4.339","volume":"4","author":"E.L. Lawler","year":"1979","unstructured":"Lawler, E.L. (1979). \u201cFast Approximation Algorithms for Knapsack Problems.\u201d Mathematics of Operations Research 4, 339\u2013356.","journal-title":"Mathematics of Operations Research"},{"key":"3448_CR99","doi-asserted-by":"crossref","first-page":"892","DOI":"10.1287\/opre.15.5.892","volume":"15","author":"C.E. Lemke","year":"1967","unstructured":"Lemke, C.E. and K. Spielberg. (1967). \u201cDirect Search Algorithms for Zero-One and Mixed-Integer Programming.\u201d Operations Research 15, 892\u2013914.","journal-title":"Operations Research"},{"key":"3448_CR100","doi-asserted-by":"crossref","unstructured":"Lokketangen, A. and F. Glover. (1996). \u201cProbabilistic Move Selection in Tabu Search for Zero-One Mixed Integer Programming Problems.\u201d In I.H. Osman and J.P. Kelly (eds.), Meta-Heuristics: Theory & Applications Kluwer Academic Publishers, pp. 467\u2013487.","DOI":"10.1007\/978-1-4613-1361-8_28"},{"key":"3448_CR101","doi-asserted-by":"crossref","first-page":"624","DOI":"10.1016\/S0377-2217(97)00295-6","volume":"106","author":"A. Lokketangen","year":"1998","unstructured":"Lokketangen, A. and F. Glover. (1998). \u201cSolving Zero-One Mixed Integer Programming Problems Using Tabu Search.\u201d Special Issue on Tabu Search, European journal of Operational Research 106, 624\u2013 658.","journal-title":"Special Issue on Tabu Search, European journal of Operational Research"},{"key":"3448_CR102","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/0969-6016(94)90031-0","volume":"1","author":"A. Lokketangen","year":"1994","unstructured":"Lokketangen, A. K. Jornsten, and S. Storoy. (1994), \u201cTabu Search Within a Pivot and Complement Framework.\u201d International transactions of Operations Research 1, 305\u2013316.","journal-title":"International transactions of Operations Research"},{"key":"3448_CR103","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1086\/294081","volume":"28","author":"J. Lorie","year":"1955","unstructured":"Lorie, J. and L.J. Savage. (1955). \u201cThree Problems in Capital Rationing.\u201d Journal of Business 28, 229\u2013 239.","journal-title":"Journal of Business"},{"key":"3448_CR104","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1287\/moor.9.2.244","volume":"9","author":"M.J. Magazine","year":"1984","unstructured":"Magazine, M.J. and M.S. Chern. (1984). \u201cA Note on Approximation Schemes for Multidimensional Knapsack Problems.\u201d Mathematics on Operations Research 9, 244\u2013247.","journal-title":"Mathematics on Operations Research"},{"key":"3448_CR105","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1016\/0377-2217(81)90175-2","volume":"8","author":"M.J. Magazine","year":"1981","unstructured":"Magazine, M.J. and O. Oguz. (1981). \u201cA Fully Polynomial Approximation Algorithm for the 0-1 Knapsack Problem.\u201d European Journal of Operational Research 8, 270\u2013273.","journal-title":"European Journal of Operational Research"},{"key":"3448_CR106","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1016\/0377-2217(84)90286-8","volume":"16","author":"M.J. Magazine","year":"1984","unstructured":"Magazine, M.J. and O. Oguz. (1984). \u201cA Heuristic Algorithm for the Multidimensional Zero-One Knapsack Problem\u201d. European Journal of Operational Research 16, 319\u2013326.","journal-title":"European Journal of Operational Research."},{"key":"3448_CR107","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1016\/0166-218X(90)90004-V","volume":"28","author":"J.W. Mamer","year":"1990","unstructured":"Mamer, J.W. and K.E. Schilling. (1990). \u201cOn the Growth of Random Knapsacks.\u201d Discrete Applied Mathematics 28, 223\u2013230.","journal-title":"Discrete Applied Mathematics"},{"key":"3448_CR108","doi-asserted-by":"crossref","first-page":"84","DOI":"10.2307\/1907744","volume":"25","author":"A.S. Manne","year":"1957","unstructured":"Manne, A.S. and H.M. Markowitz. (1957). \u201cOn the Solution of Discrete Programming Problems.\u201d Econometrica 25, 84\u2013110.","journal-title":"Econometrica"},{"key":"3448_CR109","unstructured":"Marsten, R.E. and T.L. Morin. (1976). \u201cMMPD, a Computer Code for Solving Multiconstraint Knapsack Problems in Integer Variables.\u201d Working paper, Operations Research Center, MIT, Cambridge, USA."},{"key":"3448_CR110","doi-asserted-by":"crossref","first-page":"1364","DOI":"10.1287\/mnsc.23.12.1364","volume":"23","author":"R.E. Marsten","year":"1977","unstructured":"Marsten, R.E. and T.L. Morin. (1977). \u201cOptimal Solutions Found for Senju and Toyoda'0\/1 Integer Programming Problems.\u201d Management Sciences 23, 1364\u20131365.","journal-title":"Management Sciences"},{"key":"3448_CR111","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/BF01588949","volume":"14","author":"R.E. Marsten","year":"1978","unstructured":"Marsten, R.E. and T.L. Morin. (1978). \u201cA Hybrid Approach to Discrete Mathematical Programming.\u201d Mathematical Programming 14, 21\u201340.","journal-title":"Mathematical Programming"},{"key":"3448_CR112","doi-asserted-by":"crossref","first-page":"633","DOI":"10.1287\/mnsc.34.5.633","volume":"34","author":"S. Martello","year":"1988","unstructured":"Martello, S. and P. Toth. (1988). \u201cA New Algorithm for the 0-1 Knapsack Problem.\u201d Management Sciences 34, 633\u2013644.","journal-title":"Management Sciences"},{"key":"3448_CR113","volume-title":"Series in Discrete Mathematics and Optimization","author":"S. Martello","year":"1990","unstructured":"Martello, S. and P. Toth. (1990). \u201cKnapsack Problems: Algorithms and Computer implementations.\u201d In Series in Discrete Mathematics and Optimization, New York. Wiley InterSciences."},{"key":"3448_CR114","doi-asserted-by":"crossref","first-page":"768","DOI":"10.1287\/opre.45.5.768","volume":"45","author":"S. Martello","year":"1997","unstructured":"Martello, S. and P. Toth. (1997). \u201cUpper Bounds and Algorithms for Hard 0-1 Knapsack Problems.\u201d Operations Research 45, 768\u2013778.","journal-title":"Operations Research"},{"key":"3448_CR115","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1016\/S0377-2217(99)00260-X","volume":"123","author":"S. Martello","year":"1999","unstructured":"Martello, S., D. Pisinger, and P. Toth. (1999). \u201cNew Trends in Exact Algorithms for the 0-1 Knapsack Problem.\u201d European Journal of Operational Research 123, 325\u2013336.","journal-title":"European Journal of Operational Research"},{"key":"3448_CR116","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1007\/BF01585741","volume":"46","author":"M. Meanti","year":"1990","unstructured":"Meanti, M., A.H.G. Rinnoy Kan, L. Stougie, and C. Vercellis. (1990). \u201cA Probabilistic Analysis of the Multiknapsack Value Function.\u201d Mathematical Programming 46, 237\u2013247.","journal-title":"Mathematical Programming"},{"key":"3448_CR117","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1287\/opre.49.2.196.13531","volume":"49","author":"H. Meier","year":"2001","unstructured":"Meier, H., N. Christofides, and G. Salkin (2001). \u201cCapital Budgeting Under Uncertainty\u2014an Integrated Approach Using Contingent Claims Analysis and Integer Programming.\u201d Operations Research 49, 196\u2013206.","journal-title":"Operations Research"},{"key":"3448_CR118","unstructured":"Nediak, M. and J. Eckstein (2001). \u201cPivot, Cut and Dive: A Heuristic for 0-1 Mixed Integer Programming.\u201d Rutcor research report, Rutgers University, USA, October 2001."},{"key":"3448_CR119","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/0167-6377(94)90013-2","volume":"15","author":"G.L. Nemhauser","year":"1993","unstructured":"Nemhauser, G.L., M.W.P. Savelsbergh, and G.C. Sigismondi. (1993). \u201cMINTO, a Mixed INTeger Optimizer.\u201d Operations Research Letters 15, 47\u201358.","journal-title":"Operations Research Letters"},{"key":"3448_CR120","doi-asserted-by":"crossref","unstructured":"Nemhauser, G.L. and L.A. Wolsey. (1988). \u201cInteger and Combinatorial Optimization.\u201d John Wiley and Sons.","DOI":"10.1002\/9781118627372"},{"key":"3448_CR121","doi-asserted-by":"crossref","unstructured":"Niar, S. and A. Fr\u00e9ville. (1997). \u201cA Parallel Tabu Search Algorithm for the 0-1 Multidimensional Knapsack Problem.\u201d International Parallel Processing Symposium'97, IEEE Computer Society Press, pp. 512\u2013516, Suisse.","DOI":"10.1109\/IPPS.1997.580948"},{"key":"3448_CR122","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1162\/neco.1993.5.2.331","volume":"5","author":"M. Ohlssen","year":"1993","unstructured":"Ohlssen, M., C. Peterson, and B. Soderberg. (1993). \u201cNeural Networks for Optimization Problems with Inequality Constraints: The Knapsack Problem.\u201d Neural Computation 5, 331\u2013339.","journal-title":"Neural Computation"},{"key":"3448_CR123","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1023\/A:1021513321301","volume":"117","author":"M.A. Osorio","year":"2002","unstructured":"Osorio, M.A., F. Glover, and P. Hammer (2002). \u201cCutting and Surrogate Constraint Analysis for Improved Multidimensional Knapsack Solutions.\u201d Annals of Operations Research 117, 71\u201393.","journal-title":"Annals of Operations Research"},{"key":"3448_CR124","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1002\/1520-6750(198704)34:2<161::AID-NAV3220340203>3.0.CO;2-A","volume":"34","author":"H. Pirkul","year":"1987","unstructured":"Pirkul, H. (1987). \u201cA Heuristic Solution Procedure for the Multiconstraint Zero-One Knapsack Problem.\u201d Naval Research Logistics 34, 161\u2013172.","journal-title":"Naval Research Logistics"},{"key":"3448_CR125","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1016\/0377-2217(94)00013-3","volume":"87","author":"D. Pisinger","year":"1995","unstructured":"Pisinger, D. (1995). \u201cAn Expanding-Core Algorithm for the Exact 0-1 Knapsack Problem.\u201d European Journal of Operational Research 87, 175\u2013187.","journal-title":"European Journal of Operational Research"},{"key":"3448_CR126","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1287\/ijoc.12.1.75.11898","volume":"12","author":"D. Pisinger","year":"2000","unstructured":"Pisinger, D. (2000). \u201cA Minimal Algorithm for the Bounded Knapsack Problem.\u201d ORSA Journal on Computing 12, 75\u201384.","journal-title":"ORSA Journal on Computing"},{"key":"3448_CR127","unstructured":"Plateau, A., D. Tachat, and P. Tolla (2001). \u201cA Hybrid Search Combining Interior Point Methods and Metaheuristics for 0-1 Programming.\u201d in Investigacion Operativa forth coming."},{"key":"3448_CR128","unstructured":"Plateau, G. (1976). \u201cR\u00e9duction de la Taille Des Probl\u00e8mes Lin\u00e9aires en Variables 0-1.\u201d Working paper, ANO-71, Universit\u00e9 de Lille 1, France."},{"key":"3448_CR129","first-page":"277","volume":"49","author":"G. Plateau","year":"1985","unstructured":"Plateau, G. and M. Elkihel. (1985). \u201cA Hybrid Method for the 0-1 Knapsack Problem.\u201d Methods of Operations Research 49, 277\u2013293.","journal-title":"Methods of Operations Research"},{"key":"3448_CR130","unstructured":"Plateau, G. and C. Roucairol. (1989). \u201cA Supercomputer Algorithm for the 0-1 Multiknapsack Problem.\u201d In R. Sharda, B. Golden, E. Wasil, O. Balei and W. Stewart, (eds.), Impacts of Recent Computer Advances on Operations Research, Operations Research Series pp. 144\u2013157."},{"key":"3448_CR131","unstructured":"Raidl G.R. (1998). \u201cAn Improved Genetic Algorithm for the Multiconstraint Knapsack Problem.\u201d in Proceedings of the 5thIEEE International Conference on Evolutionary Computation pp. 207\u2013211."},{"key":"3448_CR132","doi-asserted-by":"crossref","unstructured":"Reilly, C.H. (1991). \u201cOptimization Test Problems with Uniformly Distributed Coefficients.\u201d Proceedings of the 1991 Winter Simulation Conference, (eds.), B.L. Nelson, W.D. Kelton and G.M. Clark, Institute of Electrical and Electronics Engineers, Phoenix, USA, 866\u2013874.","DOI":"10.1109\/WSC.1991.185697"},{"key":"3448_CR133","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1016\/0166-218X(93)90051-O","volume":"42","author":"Kan A.H.G. Rinnoy","year":"1993","unstructured":"Rinnoy, Kan A.H.G., L. Stougie, and C. Vercellis. (1993). \u201cA Class of Generalized Greedy Algorithms for the Multi-Knapsack Problem.\u201d Discrete applied Mathematics 42, 279\u2013290.","journal-title":"Discrete applied Mathematics"},{"key":"3448_CR134","doi-asserted-by":"crossref","first-page":"445","DOI":"10.1287\/ijoc.6.4.445","volume":"6","author":"M.W.P. Savelsbergh","year":"1994","unstructured":"Savelsbergh, M.W.P. (1994). \u201cPreprocessing and Probing Techniques for Mixed Integer Programming Problems.\u201d ORSA Journal of Computing 6, 445\u2013454.","journal-title":"ORSA Journal of Computing"},{"key":"3448_CR135","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/0377-2217(90)90303-S","volume":"46","author":"K.E. Schilling","year":"1990","unstructured":"Schilling, K.E. (1990). \u201cThe Growth of m-Constraint Random Knapsacks.\u201d European Journal of Operational Research 46, 109\u2013112.","journal-title":"European Journal of Operational Research"},{"key":"3448_CR136","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/0166-218X(92)00125-6","volume":"48","author":"K.E. Schilling","year":"1994","unstructured":"Schilling, K.E. (1994). \u201cRandom Knapsacks with Many Constraints.\u201d Discrete Applied Mathematics 48, 163\u2013174.","journal-title":"Discrete Applied Mathematics"},{"key":"3448_CR137","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1287\/mnsc.15.4.B196","volume":"15","author":"S. Senju","year":"1968","unstructured":"Senju, S. and Y. Toyada. (1968). \u201cAn Approach to Linear Programming Problems with 0-1 Variables.\u201d Management Sciences 15, 196\u2013207.","journal-title":"Management Sciences"},{"key":"3448_CR138","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1145\/321864.321873","volume":"22","author":"S. Shani","year":"1975","unstructured":"Shani, S. (1975). \u201cApproximate Algorithms for the 0-1 Knapsack Problem.\u201d Journal of Association for Computing Machinery 22, 115\u2013124.","journal-title":"Journal of Association for Computing Machinery"},{"key":"3448_CR139","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1057\/jors.1979.78","volume":"30","author":"W. Shih","year":"1979","unstructured":"Shih, W. (1979). \u201cA Branch and Bound Method for the Multiconstraint Zero-One Knapsack Problem.\u201d Journal of Operations Research Society 30, 369\u2013378.","journal-title":"Journal of Operations Research Society"},{"key":"3448_CR140","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/0377-2217(78)90093-0","volume":"2","author":"A.L. Soyster","year":"1978","unstructured":"Soyster, A.L., B. Lev and W. Slivka. (1978). \u201cZero-One Programming with Many Variables and Few Constraints.\u201d European Journal of Operational Research 2, 195\u2013201.","journal-title":"European Journal of Operational Research"},{"key":"3448_CR141","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/0377-2217(94)90164-3","volume":"73","author":"K. Szkatula","year":"1994","unstructured":"Szkatula, K. (1994). \u201cThe Growth of Multi-Constraint Random Knapsacks with Various Right-Hand Sides of the Constraints.\u201d European Journal of Operational Research 73, 199\u2013204.","journal-title":"European Journal of Operational Research"},{"key":"3448_CR142","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/S0167-6377(97)00024-2","volume":"21","author":"K. Szkatula","year":"1997","unstructured":"Szkatula, K. (1997). \u201cThe Growth of Multi-Constraint Random Knapsacks with Large Right-Hand Sides of the Constraints.\u201d Operations Research Letters 21, 25\u201330.","journal-title":"Operations Research Letters"},{"key":"3448_CR143","unstructured":"Szkatula, K. (2000). \u201cHow Fast the Random Knapsacks with Many Constraints Grow.\u201d Working paper presented at ECCO XIII conference, Capri, Italy."},{"key":"3448_CR144","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1002\/nav.3800220210","volume":"22","author":"A. Thesen","year":"1975","unstructured":"Thesen, A. (1975). \u201cA Recursive Branch and Bound Algorithm for the Multidimensional Knapsack Problem.\u201d Naval Research Quaterly 22, 341\u2013353.","journal-title":"Naval Research Quaterly"},{"key":"3448_CR145","first-page":"226","volume":"32","author":"J. Thiel","year":"1994","unstructured":"Thiel, J. and S. Voss. (1994). \u201cSome Experiences on Solving Multiconstraint Zero-One Knapsack Problems with Genetic Algorithms.\u201d INFOR 32, 226\u2013242.","journal-title":"INFOR"},{"key":"3448_CR146","doi-asserted-by":"crossref","unstructured":"Toulouse, M., T.G. Crainic, and M. Gendreau. (1996). \u201cCommunication Issues in Designing Cooperative Multithread Parallel Searches.\u201d In I.H. Osman and J.P. Kelly (eds.), Meta-Heuristics : Theory and Applications Kluwer Academic Publishers, pp. 503\u2013522.","DOI":"10.1007\/978-1-4613-1361-8_30"},{"key":"3448_CR147","doi-asserted-by":"crossref","unstructured":"[177] Toyoda, Y. (1975). \u201cA Simplified Algorithm for Obtaining Approximate Solutions to Zero-One Programming Problems.\u201d Management Sciences 21, 1417\u20131427.","DOI":"10.1287\/mnsc.21.12.1417"},{"key":"3448_CR148","unstructured":"Vasquez, M. and J.K. Hao (2001a). \u201cA Logic-Constrained Knapsack Formulation and a Tabu Algorithm for the Daily Photograph Scheduling of an Earth Observation Satellite.\u201d Journal of Computational Optimization and Applications forth coming."},{"key":"3448_CR149","doi-asserted-by":"crossref","unstructured":"Vasquez, M. and J.K. Hao (2001b). \u201cUne Approche Hybride Pour le Sac \u00e0 dos Multidimensionnel en Variables 0-1.\u201d in RAIRO Operations Research forthcoming.","DOI":"10.1051\/ro:2001123"},{"key":"3448_CR150","unstructured":"Voss, S. (1993). \u201cTabu Search: Applications and Prospects.\u201d In: D.Z. Du and P.M. Pardalos, (eds.), Network Optimization Problems pp. 333\u2013353."},{"key":"3448_CR151","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1287\/opre.15.1.83","volume":"15","author":"H.M. Weingartner","year":"1967","unstructured":"Weingartner, H.M. and D.N. Ness. (1967). \u201cMethod for the Solution for the Multidimensional 0-1 Knapsack Problem.\u201d Operations Research 15, 83\u2013103.","journal-title":"Operations Research"},{"key":"3448_CR152","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/BFb0120913","volume":"13","author":"L.A. Wolsey","year":"1980","unstructured":"Wolsey, L.A. (1980). \u201cHeuristic Analysis, Linear Programming and Branch and Bound.\u201d Mathematical Programming Study 13, 121\u2013134.","journal-title":"Mathematical Programming Study"},{"key":"3448_CR153","unstructured":"Yang, J. (1994). \u201cA Computational Study on 0-1 Knapsack Problems Generated Under Explicit Correlation Induction.\u201d MS Thesis, Department of Industrial and Systems Engineering, The Ohio State University, Columbus, USA."}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-005-3448-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10479-005-3448-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-005-3448-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T17:59:34Z","timestamp":1559152774000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10479-005-3448-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,10]]},"references-count":153,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2005,10]]}},"alternative-id":["3448"],"URL":"https:\/\/doi.org\/10.1007\/s10479-005-3448-8","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"value":"0254-5330","type":"print"},{"value":"1572-9338","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,10]]}}}