Affordable Access

Publisher Website

A Bound and Bound algorithm for the zero-one multiple knapsack problem

Authors
Journal
Discrete Applied Mathematics
0166-218X
Publisher
Elsevier
Publication Date
Volume
3
Issue
4
Identifiers
DOI: 10.1016/0166-218x(81)90005-6
Disciplines
  • Computer Science

Abstract

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.

There are no comments yet on this publication. Be the first to share your thoughts.