Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimality. (English) Zbl 0571.90065
The multiconstraint 0-1 knapsack problem is encountered when one has to decide how to use a knapsack with multiple resource constraints. Even though the single constraint version of this problem has received a lot of attention, the multiconstraint knapsack problem has been seldom addressed.
This paper deals with developing an effective solution procedure for the multiconstraint knapsack problem. Various relaxations of the problem are suggested and theoretical relations between these relaxations are pointed out. Detailed computational experiments are carried out to compare bounds produced by these relaxations. New algorithms for obtaining surrogate bounds are developed and tested. Rules for reducing problem size are suggested and shown to be effective through computational tests. Different separation, branching and bounding rules are compared using an experimental branch and bound code. An efficient branch and bound procedure is developed, tested and compared with two previously developed optimal algorithms. Solution times with the new procedure are found to be considerably lower. This procedure can also be used as a heuristic for large problems by early termination of the search tree. This scheme was tested and found to be very effective.
This paper deals with developing an effective solution procedure for the multiconstraint knapsack problem. Various relaxations of the problem are suggested and theoretical relations between these relaxations are pointed out. Detailed computational experiments are carried out to compare bounds produced by these relaxations. New algorithms for obtaining surrogate bounds are developed and tested. Rules for reducing problem size are suggested and shown to be effective through computational tests. Different separation, branching and bounding rules are compared using an experimental branch and bound code. An efficient branch and bound procedure is developed, tested and compared with two previously developed optimal algorithms. Solution times with the new procedure are found to be considerably lower. This procedure can also be used as a heuristic for large problems by early termination of the search tree. This scheme was tested and found to be very effective.
MSC:
| 90C10 | Integer programming |
| 90C09 | Boolean programming |
| 65K05 | Numerical mathematical programming methods |
Keywords:
multiconstraint 0-1 knapsack problem; multiple resource constraints; solution procedure; relaxations; computational experiments; surrogate bounds; branch and boundSoftware:
SCICONICReferences:
| [1] | E. Balas and E. Zemel, ”An algorithm for large zero-one knapsack problems”,Operations Research 28 (1980) 1130–1154. · Zbl 0449.90064 · doi:10.1287/opre.28.5.1130 |
| [2] | E. Balas and G. H. Martin, ”Pivot and complement–A heuristic for 0–1 programming”,Management Science 26 (1980) 86–96. · Zbl 0442.90060 · doi:10.1287/mnsc.26.1.86 |
| [3] | R. L. Bulfin, P. G. Parker and C. M. Shetty, ”Computational results with a branch and bound algorithm for the general knapsack problem”,Naval Research Logistics Quarterly 26 (1979) 41–46. · Zbl 0396.90064 · doi:10.1002/nav.3800260105 |
| [4] | A. V. Cabot, ”An enumeration algorithm for knapsack problems”,Operations Research 18 (1970) 306–311. · Zbl 0195.20801 · doi:10.1287/opre.18.2.306 |
| [5] | L. G. Chalmet and L. F. Gelders, ”Lagrangian relaxations for a generalized assignment-type problem” Proceedings of Second European Congress on Operations Research (North-Holland, 1976) pp. 103–109. · Zbl 0373.90070 |
| [6] | M. E. Dyer, ”Calculating surrogate constraints”,Mathematical Programming 19 (1980) 255–278. · Zbl 0464.90067 · doi:10.1007/BF01581647 |
| [7] | D. Erlenkotter, ”A dual based procedure for uncapacitated facility location”,Operations Research 26 (1978) 992–1009. · Zbl 0422.90053 · doi:10.1287/opre.26.6.992 |
| [8] | H. Everett, ”Generalized lagrange multiplier method for solving problems of optimum allocation of resources”,Operations Research 11 (1963) 399–417. · Zbl 0113.14202 · doi:10.1287/opre.11.3.399 |
| [9] | B. Gavish, ”On obtaining the ’best’ multipliers for a lagrangian relaxation for integer programming”,Computers and Operations Research 5 (1978) 55–71. · doi:10.1016/0305-0548(78)90018-7 |
| [10] | B. Gavish, ”Topological design of centralized computer networks–Formulations and algorithms”,Networks 12 (1982) 355–377. · Zbl 0493.94021 · doi:10.1002/net.3230120402 |
| [11] | B. Gavish, ”Formulations and algorithms for the capacitated minimal directed tree problem”,Journal of the Association for Computing Machinery 30 (1983) 118–132. · Zbl 0504.90052 |
| [12] | B. Gavish and S. L. Hantler, ”An algorithm for optimal route selection in SNA networks”,IEEE Transactions on Communications 31 (1983) 1154–1161. · doi:10.1109/TCOM.1983.1095752 |
| [13] | B. Gavish and H. Pirkul, ”Allocation of data bases and processors in a distributed computing system” in: J. Akoka, ed.,Management of distributed data processing (North-Holland, 1982) pp. 215–231. |
| [14] | B. Gavish and H. Pirkul, ”Models for computer and file allocation in distributed computer networks”, Working Paper, The Graduate School of Management, The University of Rochester (Rochester, 1983). |
| [15] | B. Gavish and H. Pirkul, ”The multiconstraint 0–1 knapsack problem”, Working Paper, The Graduate School of Management, The University of Rochester (Rochester, 1981). |
| [16] | B. Gavish and K. N. Srikanth, ”An optimal solution method for the multiple travelling salesman problem”, Working Paper, The Graduate School of Management, The University of Rochester (Rochester, 1980). |
| [17] | A. M. Geoffrion, ”Lagrangian relaxation and its uses in integer programming”,Mathematical Programming Study 2 (1974) 82–114. |
| [18] | A. M. Geoffrion and R. McBride, ”Lagrangian relaxation applied to capacitated facility location problems”,AIIE Transactions 10 (1978) 40–47. |
| [19] | P. C. Gilmore and R. E. Gomory, ”Thoery and computation of knapsack problems”,Operations Research 14 (1966) 1045–1074. · Zbl 0173.21502 · doi:10.1287/opre.14.6.1045 |
| [20] | F. Glover, ”A multiphase dual algorithm for the zero-one integer programming problem”,Operations Research 13 (1965) 879–919. · Zbl 0163.41301 · doi:10.1287/opre.13.6.879 |
| [21] | F. Glover, ”Surrogate constraint duality in mathematical programming”,Operations Research 23 (1975) 434–453. · Zbl 0314.90093 · doi:10.1287/opre.23.3.434 |
| [22] | C. J. Green, ”Two algorithms for solving independent multidimensional knapsack problems”, Management Science Research Report No. 110, Carnegie Institute of Technology, Graduate School of Inductrial Administration (Pittsburgh, 1967). |
| [23] | H. J. Greenberg, ”The generalized penalty-function/surrogate model”,Operations Research 21 (1973) 162–178. · Zbl 0261.90056 · doi:10.1287/opre.21.1.162 |
| [24] | H. J. Greenberg and W. P. Pierskalla, ”Surrogate mathematical programming”,Operations Research 18 (1970) 924–939 · Zbl 0232.90059 · doi:10.1287/opre.18.5.924 |
| [25] | M. Held and R. M. Karp, ”The travelling salesman problem and minimum spanning trees”,Operations Research 18 (1970) 1138–1162. · Zbl 0226.90047 · doi:10.1287/opre.18.6.1138 |
| [26] | M. Held, P. Wolfe and H. P. Crowder, ”Validation of subgradient optimization”,Mathematical Programming 5 (1974) 62–88. · Zbl 0284.90057 · doi:10.1007/BF01580223 |
| [27] | E. Horowitz and S. Sahni, ”Computing partitions with applications to the knapsack problem”,Journal of the Association for Computing Machinery 21 (1974) 277–292. · Zbl 0329.90046 |
| [28] | G. P. Ingargiola and J. F. Korsh, ”Reduction algorithm for zero-one single knapsack problems”,Management Science 20 (1973) 460–463. · Zbl 0304.90082 · doi:10.1287/mnsc.20.4.460 |
| [29] | M. H. Karwan, ”Surrogate constraint duality and extensions in integer programming”, Ph. D. Dissertation, School of Industrial and Systems Engineering, Georgia Institute of Technology (Atlanta, 1976). |
| [30] | M. H. Karwan and R. L. Rardin, ”Some relationships between lagrangian and surrogate duality in integer programming”,Mathematical Programming 18 (1979) 320–334. · Zbl 0421.90056 · doi:10.1007/BF01588253 |
| [31] | M. H. Karwan and R. L. Rardin, ”Searchability of composite and multiple surrogate dual functions”, Working Paper, School of Industrial and Systems Engineering., Georgia Institute of Technology (Atlanta, 1978). · Zbl 0449.90068 |
| [32] | A. H. Land and S. Powell, ”Fortran Codes for mathematical programming linear, quadratic and discrete”, Wiley (London, 1973). · Zbl 0278.68036 |
| [33] | R. Loulou and E. Michaelides, ”New greedy-like heuristics for the multidimensional 0–1 knapsack problem”,Operations Research 27 (1979) 1101–1114. · Zbl 0442.90058 · doi:10.1287/opre.27.6.1101 |
| [34] | D. G. Luenberger, ”Quasi-convex programming”,Siam Journal of Applied Mathematics 16 (1968) 1090–1095. · Zbl 0212.23905 · doi:10.1137/0116088 |
| [35] | S. Martello and P. Toth, ”An upperbound for the zero-one knapsack problem and a branch and bound algorithm”,European Journal of Operational Research 1 (1977) 168–175. · Zbl 0374.90050 · doi:10.1016/0377-2217(77)90024-8 |
| [36] | R. M. Nauss, ”An efficient algorithm for the 0–1 knapsack problem”,Management Science 23 (1976) 27–31. · Zbl 0337.90042 · doi:10.1287/mnsc.23.1.27 |
| [37] | H. M. Salkin and C. A. Kluyver, ”The knapsack problem, a survey”,Naval Research Logistics Quarterly 22 (1975) 127–144. · Zbl 0305.90038 · doi:10.1002/nav.3800220110 |
| [38] | W. Shih, ”A branch and bound method for the multiconstraint zero-one knapsack problem”,Journal of Operational Research Society 30 (1979) 369–378. · Zbl 0411.90050 |
| [39] | 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–201. · Zbl 0381.90076 · doi:10.1016/0377-2217(78)90093-0 |
| [40] | Users Guide to Scionic/VM (Version 1–2), Scicon Computer Services, Ltd., Brick Close, Kiln Farm, Milton Keynes MK11 3EJ, U.K. |
| [41] | H. M. Weingartner and D. N. Ness, ”Methods for the solution of the multidimensional 0–1 knapsack problem”,Operations Research 15 (1967) 83–103. · doi:10.1287/opre.15.1.83 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
