(A) study on algorithm for the multiconstraint 0-1 knapsack problem

Abstract

The Multiconstraint 0-1 Knapsack Problem(MCKP) is encountered when one has to decide how to make efficient use of an entity which consumes multiple resources. Unlike the single constraint version of this problem, the MCKP has been seldom addressed in spite of its wide applicability. In this study, the algorithm for the MCKP to optimality is discussed. Main emphasis is on the efficient problem reduction methods which fix as many variables as possible prior to the implicit enumeration phase with small computational burden. The computational results related to the each section are reported.