Efficient Algorithms for the Multiconstraint General Knapsack Problem

References

• Akinc , Umit , “ An Algorithm for the knapsack problem ”, IIE Transactions , 15 , 1 ( 1983 ).
   Web of Science ®Google Scholar
• Balas , E. and Zemel , E. , “ An algorithm for large zero-one knapsack problems ”, Operations Research ( 1980 ) 28 , 5 , 1130 – 1154 .
   Web of Science ®Google Scholar
• Bulfin , R. L. , Parker , P. G. and Shetty , C. M. , “ Computational results with a branch and bound algorithm for the general knapsack problem ”, Naval Research Logistics Quarterly , 26 , 41 – 46 ( 1979 ).
   Google Scholar
• Cabot , A. V. , “ An enumeration algorithm for knapsack problems ”, Operations Research , 18 , 306 – 311 ( 1970 ).
   Web of Science ®Google Scholar
• Chalmet , L. G. and Gelders , L. F. , “ Lagrangean relaxations for a generalized assignment-type problem ”, Proc. Second European Congress on Operations Research , North Holland, Amsterdam, 103–109 ( 1976 ).
   Google Scholar
• Dyer , M. E. , “ Calculating surrogate constraints ”, Mathematical Programming , 19 , 255 – 278 ( 1980 ).
   Web of Science ®Google Scholar
• Erlenkotter , D. , “ A dual based procedure for uncapacitated facility location ”, Operations Research ( 1978 ) 26 , 1 , 992 – 1009 .
   Web of Science ®Google Scholar
• Gavish , B. , “ On obtaining the ‘best’ multipliers for a lagrangean relaxation for integer programming ”, Computers and Operations Research , 5 , 55 – 71 ( 1978 ).
   Web of Science ®Google Scholar
• Gavish , B. , “ Topological design of centralized computer networks –- formulations and algorithms ”, Networks , 12 , 355 – 377 ( 1982 ).
   Web of Science ®Google Scholar
• Gavish , B. , “ Formulations and algorithms for the capacitated minimal directed tree problem ”, Journal of the Association for Computing Machinery ( 1983 ) 30 , 1 , 118 – 132 .
   Web of Science ®Google Scholar
• Gavish , B. and Hantler , S. L. , “ An algorithm for optimal route selection in SNA networks ”, IEEE Trans, on Comp. Comm. , 31 , 1154 – 1161 ( 1983 ).
   Web of Science ®Google Scholar
• Gavish , B. and Pirkul , H. , “ Allocation of data bases and processors in a distributed computing system ”, Management of Distributed Data Processing ( Akoka , J. ), North Holland , 215–231 ( 1982 ) .
   Google Scholar
• Gavish , B. and Pirkul , H. , “ Efficient Algorithms for solving multiconstraint zero-one knapsack problems to optimality ”, Mathematical Programming , 31 , 78 – 105 ( 1985 ).
   Web of Science ®Google Scholar
• Geoffrion , A. M. , “ Lagrangean relaxation and its uses in integer programming ”, Mathematical Programming Study , 2 , 82 – 114 ( 1974 ).
   Google Scholar
• Geoffrion , A. M. , and McBride , R. , “ Lagrangean relaxation applied to capacitated facility location problems ”, AIIE Transactions , 10 , 40 – 47 ( 1978 ).
   Web of Science ®Google Scholar
• Gilmore , P. C. and Gomory , R. , “ A linear programming approach to the stock cutting problem, Part 11 ”, Operations Research , 21 , 863 – 888 ( 1973 ).
   Google Scholar
• Gilmore , P. C. and Gomory , R. , “ The theory and computations of knapsack problems ”, Operations Research , 14 , 1045 – 1074 ( 1966 ).
   Web of Science ®Google Scholar
• Glover , F. , “ A multiphase dual algorithm for the zero-one integer programming problem ”, Operations Research , 13 , 879 – 919 ( 1965 ).
   Web of Science ®Google Scholar
• Glover , F. , “ Surrogate constraint duality in mathematical programming ”, Operations Research ( 1975 ) 23 , 3 , 434 – 453 .
   Web of Science ®Google Scholar
• Glover , F. , Karney , D. and Ktingman , D. , “ A study of alternative relaxation approaches for a manpower planning problem ”, Quantitative Planning and Control , Ijiri Y. and Whinston , A. B. , Academic Press , 141–164 ( 1979 ) .
   Google Scholar
• Green , C. J. , “ Two algorithms for solving independent multidimensional knapsack problems ”, Management Science Research Report No. 110, Carnegie Institute of Technology, Graduate School of Industrial Administration ( 1967 ) .
   Google Scholar
• Greenberg , H. J. and Pierskalla , W. P. , “ Surrogate mathematical programming ,” Operations Research , 18 , 924 – 939 ( 1970 ).
   Web of Science ®Google Scholar
• Held , M. and Karp , R. M. , “ The travelling salesman problem and minimum spanning trees ”, Operations Research , 18 , 1138 – 1162 ( 1970 ).
   Web of Science ®Google Scholar
• Held , M. , Wolfe , P. and Crowder , H. P. , “ Validation of sub-gradient optimization ”, Mathematical Programming ( 1974 ) 5 , 1 , 62 – 68 .
   Google Scholar
• Horowitz , E. and Sahni , S. , “ Computing partitions with applications to the knapsack problem ”, Journal of the Association for Computing Machinery ( 1974 ) 21 , 2 , 277 – 292 .
   Web of Science ®Google Scholar
• Ingargiola , G. P. and Korsh , J. F. , “ Reduction algorithm for zero-one single knapsack problems ”, Management Science ( 1973 ) 20 , 4 , 460 – 463 .
   Web of Science ®Google Scholar
• Karwan , M. H. and Rardin , R. L. , “ Some relationships between Lagrangean and surrogate duality in integer programming ”, Mathematical Programming , 18 , 320 – 334 ( 1979 ).
   Web of Science ®Google Scholar
• Martello , S. and Toth , P. “ An upperbound for the zero-one knapsack problem and a branch and bound algorithm ”, European Journal of Operational Research 1 , 168 174 ( 1977 ).
   Google Scholar
• Nauss , R. M. , “ An efficient algorithm for the 0–1 knapsack problem ”, Management Science ( 1976 ) 23 , 1 , 27 – 31 .
   Web of Science ®Google Scholar
• Pirkul , H. , “ Allocating users and their databases among processing sites of a distributed computer System ”, European Journal of Operational Research (to appear).
   Google Scholar
• Pirkul , H. and Aras , O. A. , “ Capacitated multiple item ordering problem with quantity discounts ”, IIE Transactions ( 1985 ) 17 , 3 , 206 – 211 .
   Web of Science ®Google Scholar
• Salkin , H. M. and Kluyver , C. A. , “ The knapsack problem, a survey ”, Naval Research Logistics Quarterly , 22 , 127 – 144 ( 1975 ).
   Google Scholar
• Shapiro , J. F. and Wagner , H. M. , “ A finite renewal algorithm for the knapsack and turnpike models ”, Operational Research , 15 , 319 – 341 ( 1967 ).
   Web of Science ®Google Scholar
• Shin , W. , “ A branch and bound method for the multiconstraint zero-one knapsack problem ”, Journal of Operational Research Society , 30 , 369 – 378 ( 1979 ).
   Web of Science ®Google Scholar
• Users Guides to Sciconic/VM (Version 1,30), Scicon Computer Services, Ltd., Brick Close, Kiln Farm, Milton Keynes MK11 3EJ. U.K. ( Sep. 1983 ).
   Google Scholar
• Weingartner , H. M. and Ness , D. N. , “ Methods for the solution of the multidimensional 0–1 knapsack problem ”, Operations Research , 15 , 83 – 103 ( 1967 ).
   Web of Science ®Google Scholar