An Algorithm for the Solution of 0-1 Loading Problems

Abstract

An enumerative algorithm is presented for the solution of 0-1 many-knapsack or loading problems. It is based on the principle that before a search is attempted as many decisions as possible should be made about inclusion or exclusion of objects from the knapsacks. This is accomplished by the introduction of a new ordering relation among the objects. This ordering relation, coupled with other relations we define, allows a drastic reduction in the extent of the search required to determine a solution.