{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,17]],"date-time":"2026-03-17T12:56:48Z","timestamp":1773752208833,"version":"3.50.1"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1985,1,1]],"date-time":"1985-01-01T00:00:00Z","timestamp":473385600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Programming"],"published-print":{"date-parts":[[1985,1]]},"DOI":"10.1007\/bf02591863","type":"journal-article","created":{"date-parts":[[2007,3,29]],"date-time":"2007-03-29T11:40:07Z","timestamp":1175168407000},"page":"78-105","source":"Crossref","is-referenced-by-count":170,"title":["Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimality"],"prefix":"10.1007","volume":"31","author":[{"given":"Bezalel","family":"Gavish","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hasan","family":"Pirkul","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF02591863_CR1","doi-asserted-by":"crossref","first-page":"1130","DOI":"10.1287\/opre.28.5.1130","volume":"28","author":"E. Balas","year":"1980","unstructured":"E. Balas and E. Zemel, \u201cAn algorithm for large zero-one knapsack problems\u201d,Operations Research 28 (1980) 1130\u20131154.","journal-title":"Operations Research"},{"key":"BF02591863_CR2","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1287\/mnsc.26.1.86","volume":"26","author":"E. Balas","year":"1980","unstructured":"E. Balas and G. H. Martin, \u201cPivot and complement\u2014A heuristic for 0\u20131 programming\u201d,Management Science 26 (1980) 86\u201396.","journal-title":"Management Science"},{"key":"BF02591863_CR3","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1002\/nav.3800260105","volume":"26","author":"R. L. Bulfin","year":"1979","unstructured":"R. L. Bulfin, P. G. Parker and C. M. Shetty, \u201cComputational results with a branch and bound algorithm for the general knapsack problem\u201d,Naval Research Logistics Quarterly 26 (1979) 41\u201346.","journal-title":"Naval Research Logistics Quarterly"},{"key":"BF02591863_CR4","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, \u201cAn enumeration algorithm for knapsack problems\u201d,Operations Research 18 (1970) 306\u2013311.","journal-title":"Operations Research"},{"key":"BF02591863_CR5","unstructured":"L. G. Chalmet and L. F. Gelders, \u201cLagrangian relaxations for a generalized assignment-type problem\u201d Proceedings of Second European Congress on Operations Research (North-Holland, 1976) pp. 103\u2013109."},{"key":"BF02591863_CR6","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1007\/BF01581647","volume":"19","author":"M. E. Dyer","year":"1980","unstructured":"M. E. Dyer, \u201cCalculating surrogate constraints\u201d,Mathematical Programming 19 (1980) 255\u2013278.","journal-title":"Mathematical Programming"},{"key":"BF02591863_CR7","doi-asserted-by":"crossref","first-page":"992","DOI":"10.1287\/opre.26.6.992","volume":"26","author":"D. Erlenkotter","year":"1978","unstructured":"D. Erlenkotter, \u201cA dual based procedure for uncapacitated facility location\u201d,Operations Research 26 (1978) 992\u20131009.","journal-title":"Operations Research"},{"key":"BF02591863_CR8","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1287\/opre.11.3.399","volume":"11","author":"H. Everett","year":"1963","unstructured":"H. Everett, \u201cGeneralized lagrange multiplier method for solving problems of optimum allocation of resources\u201d,Operations Research 11 (1963) 399\u2013417.","journal-title":"Operations Research"},{"key":"BF02591863_CR9","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/0305-0548(78)90018-7","volume":"5","author":"B. Gavish","year":"1978","unstructured":"B. Gavish, \u201cOn obtaining the \u2018best\u2019 multipliers for a lagrangian relaxation for integer programming\u201d,Computers and Operations Research 5 (1978) 55\u201371.","journal-title":"Computers and Operations Research"},{"key":"BF02591863_CR10","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1002\/net.3230120402","volume":"12","author":"B. Gavish","year":"1982","unstructured":"B. Gavish, \u201cTopological design of centralized computer networks\u2014Formulations and algorithms\u201d,Networks 12 (1982) 355\u2013377.","journal-title":"Networks"},{"key":"BF02591863_CR11","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1145\/322358.322367","volume":"30","author":"B. Gavish","year":"1983","unstructured":"B. Gavish, \u201cFormulations and algorithms for the capacitated minimal directed tree problem\u201d,Journal of the Association for Computing Machinery 30 (1983) 118\u2013132.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"BF02591863_CR12","doi-asserted-by":"crossref","first-page":"1154","DOI":"10.1109\/TCOM.1983.1095752","volume":"31","author":"B. Gavish","year":"1983","unstructured":"B. Gavish and S. L. Hantler, \u201cAn algorithm for optimal route selection in SNA networks\u201d,IEEE Transactions on Communications 31 (1983) 1154\u20131161.","journal-title":"IEEE Transactions on Communications"},{"key":"BF02591863_CR13","unstructured":"B. Gavish and H. Pirkul, \u201cAllocation of data bases and processors in a distributed computing system\u201d in: J. Akoka, ed.,Management of distributed data processing (North-Holland, 1982) pp. 215\u2013231."},{"key":"BF02591863_CR14","series-title":"Working Paper","volume-title":"Models for computer and file allocation in distributed computer networks","author":"B. Gavish","year":"1983","unstructured":"B. Gavish and H. Pirkul, \u201cModels for computer and file allocation in distributed computer networks\u201d, Working Paper, The Graduate School of Management, The University of Rochester (Rochester, 1983)."},{"key":"BF02591863_CR15","series-title":"Working Paper","volume-title":"The multiconstraint 0\u20131 knapsack problem","author":"B. Gavish","year":"1981","unstructured":"B. Gavish and H. Pirkul, \u201cThe multiconstraint 0\u20131 knapsack problem\u201d, Working Paper, The Graduate School of Management, The University of Rochester (Rochester, 1981)."},{"key":"BF02591863_CR16","series-title":"Working Paper","volume-title":"An optimal solution method for the multiple travelling salesman problem","author":"B. Gavish","year":"1980","unstructured":"B. Gavish and K. N. Srikanth, \u201cAn optimal solution method for the multiple travelling salesman problem\u201d, Working Paper, The Graduate School of Management, The University of Rochester (Rochester, 1980)."},{"key":"BF02591863_CR17","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1007\/BFb0120690","volume":"2","author":"A. M. Geoffrion","year":"1974","unstructured":"A. M. Geoffrion, \u201cLagrangian relaxation and its uses in integer programming\u201d,Mathematical Programming Study 2 (1974) 82\u2013114.","journal-title":"Mathematical Programming Study"},{"key":"BF02591863_CR18","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1080\/05695557808975181","volume":"10","author":"A. M. Geoffrion","year":"1978","unstructured":"A. M. Geoffrion and R. McBride, \u201cLagrangian relaxation applied to capacitated facility location problems\u201d,AIIE Transactions 10 (1978) 40\u201347.","journal-title":"AIIE Transactions"},{"key":"BF02591863_CR19","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 R. E. Gomory, \u201cThoery and computation of knapsack problems\u201d,Operations Research 14 (1966) 1045\u20131074.","journal-title":"Operations Research"},{"key":"BF02591863_CR20","doi-asserted-by":"crossref","first-page":"879","DOI":"10.1287\/opre.13.6.879","volume":"13","author":"F. Glover","year":"1965","unstructured":"F. Glover, \u201cA multiphase dual algorithm for the zero-one integer programming problem\u201d,Operations Research 13 (1965) 879\u2013919.","journal-title":"Operations Research"},{"key":"BF02591863_CR21","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1287\/opre.23.3.434","volume":"23","author":"F. Glover","year":"1975","unstructured":"F. Glover, \u201cSurrogate constraint duality in mathematical programming\u201d,Operations Research 23 (1975) 434\u2013453.","journal-title":"Operations Research"},{"key":"BF02591863_CR22","series-title":"Management Science Research Report","volume-title":"Two algorithms for solving independent multidimensional knapsack problems","author":"C. J. Green","year":"1967","unstructured":"C. J. Green, \u201cTwo algorithms for solving independent multidimensional knapsack problems\u201d, Management Science Research Report No. 110, Carnegie Institute of Technology, Graduate School of Inductrial Administration (Pittsburgh, 1967)."},{"key":"BF02591863_CR23","doi-asserted-by":"crossref","first-page":"162","DOI":"10.1287\/opre.21.1.162","volume":"21","author":"H. J. Greenberg","year":"1973","unstructured":"H. J. Greenberg, \u201cThe generalized penalty-function\/surrogate model\u201d,Operations Research 21 (1973) 162\u2013178.","journal-title":"Operations Research"},{"key":"BF02591863_CR24","doi-asserted-by":"crossref","first-page":"924","DOI":"10.1287\/opre.18.5.924","volume":"18","author":"H. J. Greenberg","year":"1970","unstructured":"H. J. Greenberg and W. P. Pierskalla, \u201cSurrogate mathematical programming\u201d,Operations Research 18 (1970) 924\u2013939","journal-title":"Operations Research"},{"key":"BF02591863_CR25","doi-asserted-by":"crossref","first-page":"1138","DOI":"10.1287\/opre.18.6.1138","volume":"18","author":"M. Held","year":"1970","unstructured":"M. Held and R. M. Karp, \u201cThe travelling salesman problem and minimum spanning trees\u201d,Operations Research 18 (1970) 1138\u20131162.","journal-title":"Operations Research"},{"key":"BF02591863_CR26","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1007\/BF01580223","volume":"5","author":"M. Held","year":"1974","unstructured":"M. Held, P. Wolfe and H. P. Crowder, \u201cValidation of subgradient optimization\u201d,Mathematical Programming 5 (1974) 62\u201388.","journal-title":"Mathematical Programming"},{"key":"BF02591863_CR27","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1145\/321812.321823","volume":"21","author":"E. Horowitz","year":"1974","unstructured":"E. Horowitz and S. Sahni, \u201cComputing partitions with applications to the knapsack problem\u201d,Journal of the Association for Computing Machinery 21 (1974) 277\u2013292.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"BF02591863_CR28","doi-asserted-by":"crossref","first-page":"460","DOI":"10.1287\/mnsc.20.4.460","volume":"20","author":"G. P. Ingargiola","year":"1973","unstructured":"G. P. Ingargiola and J. F. Korsh, \u201cReduction algorithm for zero-one single knapsack problems\u201d,Management Science 20 (1973) 460\u2013463.","journal-title":"Management Science"},{"key":"BF02591863_CR29","volume-title":"Surrogate constraint duality and extensions in integer programming","author":"M. H. Karwan","year":"1976","unstructured":"M. H. Karwan, \u201cSurrogate constraint duality and extensions in integer programming\u201d, Ph. D. Dissertation, School of Industrial and Systems Engineering, Georgia Institute of Technology (Atlanta, 1976)."},{"key":"BF02591863_CR30","doi-asserted-by":"crossref","first-page":"320","DOI":"10.1007\/BF01588253","volume":"18","author":"M. H. Karwan","year":"1979","unstructured":"M. H. Karwan and R. L. Rardin, \u201cSome relationships between lagrangian and surrogate duality in integer programming\u201d,Mathematical Programming 18 (1979) 320\u2013334.","journal-title":"Mathematical Programming"},{"key":"BF02591863_CR31","series-title":"Working Paper","volume-title":"Searchability of composite and multiple surrogate dual functions","author":"M. H. Karwan","year":"1978","unstructured":"M. H. Karwan and R. L. Rardin, \u201cSearchability of composite and multiple surrogate dual functions\u201d, Working Paper, School of Industrial and Systems Engineering., Georgia Institute of Technology (Atlanta, 1978)."},{"key":"BF02591863_CR32","volume-title":"Fortran Codes for mathematical programming linear, quadratic and discrete","author":"A. H. Land","year":"1973","unstructured":"A. H. Land and S. Powell, \u201cFortran Codes for mathematical programming linear, quadratic and discrete\u201d, Wiley (London, 1973)."},{"key":"BF02591863_CR33","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, \u201cNew greedy-like heuristics for the multidimensional 0\u20131 knapsack problem\u201d,Operations Research 27 (1979) 1101\u20131114.","journal-title":"Operations Research"},{"key":"BF02591863_CR34","doi-asserted-by":"crossref","first-page":"1090","DOI":"10.1137\/0116088","volume":"16","author":"D. G. Luenberger","year":"1968","unstructured":"D. G. Luenberger, \u201cQuasi-convex programming\u201d,Siam Journal of Applied Mathematics 16 (1968) 1090\u20131095.","journal-title":"Siam Journal of Applied Mathematics"},{"key":"BF02591863_CR35","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1016\/0377-2217(77)90024-8","volume":"1","author":"S. Martello","year":"1977","unstructured":"S. Martello and P. Toth, \u201cAn upperbound for the zero-one knapsack problem and a branch and bound algorithm\u201d,European Journal of Operational Research 1 (1977) 168\u2013175.","journal-title":"European Journal of Operational Research"},{"key":"BF02591863_CR36","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1287\/mnsc.23.1.27","volume":"23","author":"R. M. Nauss","year":"1976","unstructured":"R. M. Nauss, \u201cAn efficient algorithm for the 0\u20131 knapsack problem\u201d,Management Science 23 (1976) 27\u201331.","journal-title":"Management Science"},{"key":"BF02591863_CR37","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1002\/nav.3800220110","volume":"22","author":"H. M. Salkin","year":"1975","unstructured":"H. M. Salkin and C. A. Kluyver, \u201cThe knapsack problem, a survey\u201d,Naval Research Logistics Quarterly 22 (1975) 127\u2013144.","journal-title":"Naval Research Logistics Quarterly"},{"key":"BF02591863_CR38","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1057\/jors.1979.78","volume":"30","author":"W. Shih","year":"1979","unstructured":"W. Shih, \u201cA branch and bound method for the multiconstraint zero-one knapsack problem\u201d,Journal of Operational Research Society 30 (1979) 369\u2013378.","journal-title":"Journal of Operational Research Society"},{"key":"BF02591863_CR39","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, \u201cZero-one programming with many variables and few constraints\u201d,European Journal of Operational Research 2 (1978) 195\u2013201.","journal-title":"European Journal of Operational Research"},{"key":"BF02591863_CR40","unstructured":"Users Guide to Scionic\/VM (Version 1\u20132), Scicon Computer Services, Ltd., Brick Close, Kiln Farm, Milton Keynes MK11 3EJ, U.K."},{"key":"BF02591863_CR41","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, \u201cMethods for the solution of the multidimensional 0\u20131 knapsack problem\u201d,Operations Research 15 (1967) 83\u2013103.","journal-title":"Operations Research"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02591863.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02591863\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02591863","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,20]],"date-time":"2019-05-20T19:37:50Z","timestamp":1558381070000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02591863"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985,1]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1985,1]]}},"alternative-id":["BF02591863"],"URL":"https:\/\/doi.org\/10.1007\/bf02591863","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[1985,1]]}}}