{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T14:26:13Z","timestamp":1759847173279,"version":"3.40.5"},"reference-count":58,"publisher":"Springer Science and Business Media LLC","issue":"1-4","license":[{"start":{"date-parts":[[2002,11,1]],"date-time":"2002-11-01T00:00:00Z","timestamp":1036108800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2002,11,1]],"date-time":"2002-11-01T00:00:00Z","timestamp":1036108800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Annals of Operations Research"],"published-print":{"date-parts":[[2002,11]]},"DOI":"10.1023\/a:1021513321301","type":"journal-article","created":{"date-parts":[[2003,3,21]],"date-time":"2003-03-21T01:44:11Z","timestamp":1048211051000},"page":"71-93","source":"Crossref","is-referenced-by-count":36,"title":["Cutting and Surrogate Constraint Analysis for Improved Multidimensional Knapsack Solutions"],"prefix":"10.1007","volume":"117","author":[{"given":"Mar\u00eda A.","family":"Osorio","sequence":"first","affiliation":[]},{"given":"Fred","family":"Glover","sequence":"additional","affiliation":[]},{"given":"Peter","family":"Hammer","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"5101700_CR1","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1287\/ijoc.6.1.82","volume":"6","author":"R. Aboudi","year":"1994","unstructured":"R. Aboudi and K. J\u00f6rnsten, Tabu search for general zero-one integer programs using the pivot and complement heuristics, ORSA Journal on Computing 6 (1994) 82\u201393.","journal-title":"ORSA Journal on Computing"},{"key":"5101700_CR2","doi-asserted-by":"crossref","first-page":"517","DOI":"10.1287\/opre.13.4.517","volume":"13","author":"E. Balas","year":"1965","unstructured":"E. Balas, An additive algorithm for solving linear programs with zero-one variables, Operations Research 13 (1965) 517\u2013546.","journal-title":"Operations Research"},{"key":"5101700_CR3","doi-asserted-by":"crossref","first-page":"915","DOI":"10.1287\/opre.15.5.915","volume":"19","author":"E. Balas","year":"1967","unstructured":"E. Balas, Discrete programming by the filter method, Operations Research 19 (1967) 915\u2013957.","journal-title":"Operations Research"},{"key":"5101700_CR4","series-title":"Manuscript","volume-title":"Optimal design of truss structures by mixed logical and linear programming","author":"S. Bollapragada","year":"1995","unstructured":"S. Bollapragada, O. Ghattas and J.N. Hooker, Optimal design of truss structures by mixed logical and linear programming, Manuscript, Graduate School of Industrial Administration, Carnegie Mellon University, Pittsburgh (1995)."},{"key":"5101700_CR5","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1287\/opre.18.2.306","volume":"18","author":"A.V. Cabot","year":"1970","unstructured":"A.V. Cabot, An enumeration algorithm for knapsack problems, Operations Research 18 (1970) 306\u2013311.","journal-title":"Operations Research"},{"key":"5101700_CR6","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1023\/A:1009642405419","volume":"4","author":"P. Chu","year":"1998","unstructured":"P. Chu and and J. Beasley, A genetic algorithm for the multidimensional knapsack problem, Journal of Heuristics 4 (1998) 63\u201386.","journal-title":"Journal of Heuristics"},{"issue":"4","key":"5101700_CR7","first-page":"219","volume":"32","author":"Y. Crama","year":"1994","unstructured":"Y. Crama and and J. Mazzola, On the strength of relaxations of multidimensional knapsack problems, INFOR 32(4) (1994) 219\u2013225.","journal-title":"INFOR"},{"key":"5101700_CR8","first-page":"31","volume":"41","author":"S. Dammeyer","year":"1993","unstructured":"S. Dammeyer and and S. Voss, Dynamic tabu list of management using reverse elimnation method, Annals of Operations Research 41 (1993) 31\u201346.","journal-title":"Dynamic tabu list of management using reverse elimnation method, Annals of Operations Research"},{"key":"5101700_CR9","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1287\/opre.5.2.266","volume":"5","author":"G.B. Dantzig","year":"1957","unstructured":"G.B. Dantzig, Discrete variables problems, Operations Research 5 (1957) 266\u2013277.","journal-title":"Operations Research"},{"key":"5101700_CR10","first-page":"49","volume":"36","author":"R. Dembo","year":"1980","unstructured":"R. Dembo and and P. Hammer, A reduction algorithm for knapsack problems, Methods of Operations Research 36 (1980) 49\u201360.","journal-title":"Methods of Operations Research"},{"key":"5101700_CR11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02242185","volume":"40","author":"A. Drexel","year":"1988","unstructured":"A. Drexel, A simulated annealing approach to the multiconstraint zero-one knapsack problem, Computing 40 (1988) 1\u20138.","journal-title":"Computing"},{"key":"5101700_CR12","first-page":"225","volume":"12","author":"H.E. Dyer","year":"1980","unstructured":"H.E. Dyer, Calculating surrogate constraints, Mathematical Programming 12 (1980) 225\u2013278.","journal-title":"Mathematical Programming"},{"key":"5101700_CR13","doi-asserted-by":"crossref","first-page":"4751","DOI":"10.1088\/0305-4470\/28\/17\/011","volume":"28","author":"J.F. Fontanari","year":"1995","unstructured":"J.F. Fontanari, A statistical analysis of the knapsack problem, Journal of Physics A:Mathematical and General 28 (1995) 4751\u20134759.","journal-title":"Journal of Physics A:Mathematical and General"},{"key":"5101700_CR14","first-page":"251","volume":"1","author":"A. Fr\u00e9ville","year":"1990","unstructured":"A. Fr\u00e9ville and and G. Plateau, Hard 0\u20131 multiknapsack test problems for size reduction methods, Investigaci\u00f3n Operativa 1 (1990) 251\u2013270.","journal-title":"Investigaci\u00f3n Operativa"},{"key":"5101700_CR15","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/0166-218X(94)90209-7","volume":"49","author":"A. Fr\u00e9ville","year":"1994","unstructured":"A. Fr\u00e9ville and and G. Plateau, An efficient preprocessing procedure for the multidimensional 0\u20131 knapsack problem, Discrete Applied Mathematics 49 (1994) 189\u2013212.","journal-title":"Discrete Applied Mathematics"},{"key":"5101700_CR16","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1007\/BF02591863","volume":"31","author":"B. Gavish","year":"1985","unstructured":"B. Gavish and and H. Pirkul, Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimality, Mathematical Programming 31 (1985) 78\u2013105.","journal-title":"Mathematical Programming"},{"key":"5101700_CR17","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1287\/opre.17.3.437","volume":"17","author":"A. Geoffrion","year":"1969","unstructured":"A. Geoffrion, An improved implicit enumeration approach for integer programming, Operations Research 17 (1969) 437\u2013454.","journal-title":"Operations Research"},{"key":"5101700_CR18","doi-asserted-by":"crossref","first-page":"1045","DOI":"10.1287\/opre.14.6.1045","volume":"14","author":"P.C. Gilmore","year":"1966","unstructured":"P.C. Gilmore and and R.E. Gomory, The theory and computation of knapsack functions, Operations Research 14 (1966) 1045\u20131075.","journal-title":"Operations Research"},{"key":"5101700_CR19","doi-asserted-by":"crossref","first-page":"879","DOI":"10.1287\/opre.13.6.879","volume":"13","author":"F. Glover","year":"1965","unstructured":"F. Glover, A multiphase-dual algorithm for the zero-one integer programming problem, Operations Research 13 (1965) 879\u2013919.","journal-title":"Operations Research"},{"key":"5101700_CR20","doi-asserted-by":"crossref","first-page":"741","DOI":"10.1287\/opre.16.4.741","volume":"16","author":"F. Glover","year":"1968","unstructured":"F. Glover, Surrogate constraints, Operations Research 16 (1968) 741\u2013749.","journal-title":"Operations Research"},{"issue":"9","key":"5101700_CR21","doi-asserted-by":"crossref","first-page":"568","DOI":"10.1287\/mnsc.17.9.568","volume":"17","author":"F. Glover","year":"1971","unstructured":"F. Glover, Flows in arborescences, Management Science 17(9) (1971) 568\u2013586.","journal-title":"Management Science"},{"issue":"3","key":"5101700_CR22","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1287\/opre.23.3.434","volume":"23","author":"F. Glover","year":"1975","unstructured":"F. Glover, Surrogate constraint duality in mathematical programming, Operations Research 23(3) (1975) 434\u2013451.","journal-title":"Operations Research"},{"key":"5101700_CR23","doi-asserted-by":"crossref","unstructured":"F. Glover and G.A. Kochenberger, Critical event tabu search for multidimensional knapsack problems, in: Meta-Heuristics: Theory and Applications, eds. I.H. Osman and J.P. Kelly (Kluwer Academic, 1996) pp. 407\u2013427.","DOI":"10.1007\/978-1-4613-1361-8_25"},{"key":"5101700_CR24","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1023\/A:1008621204567","volume":"8","author":"F. Glover","year":"1997","unstructured":"F. Glover, H. Sherali and Y. Lee, Generating cuts from surrogate constraint analysis for zero-one and multiple choice programming, Computational Optimization and Applications 8 (1997) 151\u2013172.","journal-title":"Computational Optimization and Applications"},{"key":"5101700_CR25","unstructured":"F. Granot and P.L. Hammer, On the use of Boolean functions in 0\u20131 linear programming, Methods of Operations Research (1971) 154\u2013184."},{"key":"5101700_CR26","doi-asserted-by":"crossref","first-page":"924","DOI":"10.1287\/opre.18.5.924","volume":"18","author":"H. Greenberg","year":"1970","unstructured":"H. Greenberg and W. Pierskalla, Surrogate mathematical programs, Operations Research 18 (1970) 924\u2013939.","journal-title":"Operations Research"},{"issue":"1","key":"5101700_CR27","first-page":"68","volume":"13","author":"P. Hammer","year":"1975","unstructured":"P. Hammer, M. Padberg and U. Peled, Constraint pairing in integer programming, INFOR 13(1) (1975) 68\u201381.","journal-title":"INFOR"},{"key":"5101700_CR28","doi-asserted-by":"crossref","first-page":"659","DOI":"10.1016\/S0377-2217(97)00296-8","volume":"106","author":"S. Hanafi","year":"1998","unstructured":"S. Hanafi and A. Fr\u00e9ville, An efficient tabu search approach for the 0\u20131 multidimensional knapsack problem, EJOR 106 (1998) 659\u2013675.","journal-title":"EJOR"},{"issue":"2","key":"5101700_CR29","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1287\/mnsc.46.2.302.11930","volume":"46","author":"R. Hill","year":"2000","unstructured":"R. Hill and Ch. Reilly, The effects of coefficient correlation structure in two-dimensional knapsack problems on solution procedure performance, Management Science 46(2) (2000) 302\u2013317.","journal-title":"Management Science"},{"key":"5101700_CR30","volume-title":"Working Paper","author":"A. Hoff","year":"1996","unstructured":"A. Hoff, A. L\u00f8kketangen and I. Mittet, Genetic algorithms for 0\/1 multidimensional knapsack problems, Working Paper, Molde College, Molde, Norway (1996)."},{"key":"5101700_CR31","doi-asserted-by":"crossref","unstructured":"J.N. Hooker, Logic-based methods for optimization, in: Principles and Practice of Constraint Programming, ed. A. Borning, Lecture Notes in Computer Science, Vol. 874 (1994) pp. 336\u2013349.","DOI":"10.1007\/3-540-58601-6_111"},{"key":"5101700_CR32","unstructured":"J.N. Hooker and N.R. Natraj, Solving 0\u20131 optimization problems with k-tree relaxation (1999), in preparation."},{"key":"5101700_CR33","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1016\/S0166-218X(99)00100-6","volume":"96\u201397","author":"J.N. Hooker","year":"1999","unstructured":"J.N. Hooker and M.A. Osorio, Mixed logical\/linear programming, Discrete Applied Mathematics 96\u201397 (1999) 395\u2013442.","journal-title":"Discrete Applied Mathematics"},{"key":"5101700_CR34","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/0305-0548(94)90089-2","volume":"21","author":"J.N. Hooker","year":"1994","unstructured":"J.N. Hooker, H. Yan, I. Grossmann and R. Raman, Logic cuts for processing networks with fixed charges, Computers and Operations Research 21 (1994) 265\u2013279.","journal-title":"Computers and Operations Research"},{"key":"5101700_CR35","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1007\/BFb0121015","volume":"22","author":"R.E. Jeroslow","year":"1984","unstructured":"R.E. Jeroslow and J.K. Lowe, Modeling with integer variables, Mathematical Programming Studies 22 (1984) 167\u2013184.","journal-title":"Mathematical Programming Studies"},{"key":"5101700_CR36","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1007\/BF01588253","volume":"17","author":"M.H. Karwan","year":"1979","unstructured":"M.H. Karwan and R.L. Rardin, Some relationships between Lagrangian and surrogate duality in integer programming, Mathematical Programming 17 (1979) 230\u2013334.","journal-title":"Mathematical Programming"},{"key":"5101700_CR37","doi-asserted-by":"crossref","unstructured":"S. Khuri, T. Back and J. Heitkotter, The zero\/one multiple knapsack problem and genetic algorithms, in: Proceedings of the 1994 ACM Symposium on Applied Computing (SAC '94) (ACM Press, 1994) pp. 188\u2013193.","DOI":"10.1145\/326619.326694"},{"key":"5101700_CR38","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1111\/j.1540-5915.1974.tb00593.x","volume":"5","author":"G. Kochenberger","year":"1974","unstructured":"G. Kochenberger, G. McCarl and F. Wymann, A heuristic for general integer programming, Decision Sciences 5 (1974) 36\u201344.","journal-title":"Decision Sciences"},{"key":"5101700_CR39","doi-asserted-by":"crossref","first-page":"176","DOI":"10.1016\/0377-2217(93)E0174-V","volume":"82","author":"M. Laguna","year":"1995","unstructured":"M. Laguna, J.P. Kelly, J.L. Gonzalez Velarde and F. Glover, Tabu search for the multilevel generalized assignment problem, European Journal of Operational Research 82 (1995) 176\u2013189.","journal-title":"European Journal of Operational Research"},{"key":"5101700_CR40","doi-asserted-by":"crossref","unstructured":"A. L\u00f8kketangen and F. Glover, Probabilistic move selection in tabu search for zero-one mixed integer programming problems, in: Meta-Heuristics: Theory and Applications, eds. I.H. Osman and J.P. Kelly (1996) pp. 467\u2013487.","DOI":"10.1007\/978-1-4613-1361-8_28"},{"key":"5101700_CR41","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1111\/1475-3995.d01-42","volume":"1","author":"A. L\u00f8kketangen","year":"1994","unstructured":"A. L\u00f8kketangen, K. J\u00f6rnsten and S. Stor\u00f8y, Tabu search within a pivot and complement framework, International Transactions of Operations Research 1 (1994) 305\u2013316.","journal-title":"International Transactions of Operations Research"},{"key":"5101700_CR42","doi-asserted-by":"crossref","first-page":"1101","DOI":"10.1287\/opre.27.6.1101","volume":"27","author":"R. Loulou","year":"1979","unstructured":"R. Loulou and E. Michaelides, New greedy-like heuristics for the multidimensional 0\u20131 knapsack problem, Operations Research 27 (1979) 1101\u20131114.","journal-title":"Operations Research"},{"issue":"2","key":"5101700_CR43","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1016\/S0377-2217(99)00260-X","volume":"123","author":"S. Martello","year":"1999","unstructured":"S. Martello, D. Pisinger and P. Toth, New trends in exact algorithms for the 0\u20131 knapsack problem, European Journal of Operational Research 123(2) (1999) 325\u2013336.","journal-title":"European Journal of Operational Research"},{"key":"5101700_CR44","volume-title":"Knapsack Problems: Algorithms and Computer Implementations","author":"S. Martello","year":"1990","unstructured":"S. Martello and P. Toth, Knapsack Problems: Algorithms and Computer Implementations (Wiley, New York, 1990)."},{"key":"5101700_CR45","doi-asserted-by":"crossref","unstructured":"M.A. Osorio and M. Laguna, Logic cuts for the multilevel generalized assignment problem (2002), to appear in European Journal of Operational Research.","DOI":"10.1016\/S0377-2217(02)00576-3"},{"issue":"1\u20133","key":"5101700_CR46","first-page":"155","volume":"8","author":"M.A. Osorio","year":"1999","unstructured":"M.A. Osorio and R. M\u00fajica, Logic cuts generation in a branch arid cut framework for location problems, Investigaci\u00f3n Operativa 8(1\u20133) (1999) 155\u2013166.","journal-title":"Investigaci\u00f3n Operativa"},{"key":"5101700_CR47","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":"H. Pirkul, A heuristic solution procedure for the multiconstraint zero-one knapsack problem, Naval Research Logistics 34 (1987) 161\u2013172.","journal-title":"Naval Research Logistics"},{"issue":"1","key":"5101700_CR48","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1287\/ijoc.12.1.75.11898","volume":"12","author":"D. Pisinger","year":"2000","unstructured":"D. Pisinger, Contributed research articles: a minimal algorithm for the bounded knapsack problem, ORSA Journal on Computing 12(1) (2000) 75\u201384.","journal-title":"ORSA Journal on Computing"},{"key":"5101700_CR49","doi-asserted-by":"crossref","unstructured":"Ch. Reilly, Input models for synthetic optimization problems, in: Proceedings of the 1999 Winter Simulation Conference (1999) pp. 116\u2013121.","DOI":"10.1145\/324138.324175"},{"key":"5101700_CR50","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/0377-2217(90)90303-S","volume":"46","author":"K.E. Schilling","year":"1990","unstructured":"K.E. Schilling, The growth of m-constraint random knapsacks, European Journal of Operations Research 46 (1990) 109\u2013112.","journal-title":"European Journal of Operations Research"},{"key":"5101700_CR51","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1287\/mnsc.15.4.B196","volume":"15","author":"S. Senju","year":"1968","unstructured":"S. Senju and Y. Toyoda, An approach to linear programming with 0\u20131 variables, Management Science 15 (1968) 196\u2013207.","journal-title":"Management Science"},{"key":"5101700_CR52","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1057\/jors.1979.78","volume":"30","author":"W. Shih","year":"1979","unstructured":"W. Shih, A branch and bound method for the multiconstraint zero-one knapsack problem, Journal of Operation Research Society of Japan 30 (1979) 369\u2013378.","journal-title":"Journal of Operation Research Society of Japan"},{"key":"5101700_CR53","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/0377-2217(78)90093-0","volume":"2","author":"A.L. Soyster","year":"1978","unstructured":"A.L. Soyster, B. Lev and W. Slivka, Zero-one programming with many variables and few constraints, European Journal of Operational Research 2 (1978) 195\u2013201.","journal-title":"European Journal of Operational Research"},{"key":"5101700_CR54","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/0377-2217(94)90164-3","volume":"73","author":"K. Szkatula","year":"1994","unstructured":"K. Szkatula, The growth of multi-constraint random knapsacks with various right-hand sides of the constraints, European Journal of Operational Research 73 (1994) 199\u2013204.","journal-title":"European Journal of Operational Research"},{"key":"5101700_CR55","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/S0167-6377(97)00024-2","volume":"21","author":"K. Szkatula","year":"1997","unstructured":"K. Szkatula, The growth of multi-constraint random knapsacks with large right-hand sides of the constraints, Operations Research Letters 21 (1997) 25\u201330.","journal-title":"Operations Research Letters"},{"key":"5101700_CR56","first-page":"226","volume":"32","author":"J. Thiel","year":"1994","unstructured":"J. Thiel and S. Voss, Some experiences on solving multiconstraint zero-one knapsack problems with genetic algorithms, INFOR 32 (1994) 226\u2013242.","journal-title":"INFOR"},{"key":"5101700_CR57","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1287\/opre.15.1.83","volume":"15","author":"H.M. Weingartner","year":"1967","unstructured":"H.M. Weingartner and D.N. Ness, Methods for the solution of the multidimensional 0\/1 knapsack problem, Operations Research 15 (1967) 83\u2013103.","journal-title":"Operations Research"},{"key":"5101700_CR58","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1016\/0377-2217(90)90302-R","volume":"46","author":"J.M. Wilson","year":"1990","unstructured":"J.M. Wilson, Generating cuts in integer programming with families of specially ordered sets, European Journal of Operational Research 46 (1990) 101\u2013108.","journal-title":"European Journal of Operational Research"}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1021513321301.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1023\/A:1021513321301\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1021513321301.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,18]],"date-time":"2025-05-18T14:16:39Z","timestamp":1747577799000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1023\/A:1021513321301"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,11]]},"references-count":58,"journal-issue":{"issue":"1-4","published-print":{"date-parts":[[2002,11]]}},"alternative-id":["5101700"],"URL":"https:\/\/doi.org\/10.1023\/a:1021513321301","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"type":"print","value":"0254-5330"},{"type":"electronic","value":"1572-9338"}],"subject":[],"published":{"date-parts":[[2002,11]]}}}