A Bound and Bound algorithm for the zero-one multiple knapsack problem |
| |
Authors: | Silvano Martello Paolo Toth |
| |
Affiliation: | Istituto di Automatica, University of Bologna, Italy |
| |
Abstract: | By the term “Bound and Bound” we define a particular tree-search technique for the ILP, which, for a maximization problem, makes use of a lower bound to determine the branches to follow in the decision tree. This technique is applied to the solution of the Zero-One Multiple Knapsack Problem and an algorithm is derived; an illustrative example of the procedure is provided. We present extensive computational results showing that the method is capable of solving problems up to 4 knapsacks and 200 variables with running times considerably smaller than those of the most commonly utilized algorithms. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|