Methods for the Solution of the Multidimensional 0/1 Knapsack Problem

In the knapsack problem, given the desirability of each of a number of items, one seeks to find that subset which satisfies a constraint on total weight. The multidimensional variant imposes constraints on additional variables of the items; the 0/1 specification means that an item is either taken or not, i.e., multiples of the same item are not considered, except possibly indirectly. Traditionally the one-dimensional knapsack problem is solved by means of dynamic programming. The multidimensional problem is usually reduced to a one-dimensional one by use of Lagrangian Multipliers that, however, do not generally yield the exact solution to the problem posed. Here some new algorithms are developed that are applied within a dynamic programming framework. Additionally, the methods make integral use of an interactive computer system in which the heuristics of the problem solver are applied and changed as the character of the solution process evolves. The problem arises in the context of capital budgeting, but has obvious applications in a variety of other areas. The methods have been employed for solving numerical problems with as many as 105 items, the parameters having been obtained from industrial applications.