AN EFFICIENT PREPROCESSING PROCEDURE FOR THE MULTIDIMENSIONAL 0-1-KNAPSACK PROBLEM

The multidimensional 0-1 knapsack problem, defined as a knapsack with multiple resource constraints, is well known to be much more difficult than the single constraint version. This paper deals with the design of an efficient preprocessing procedure for large-scale instances. The algorithm provides sharp lower and upper bounds on the optimal value, and also a tighter equivalent representation by reducing the continuo us feasible set and by eliminating constraints and variables. This sch eme is shown to be very effective through a lot of computational exper iments with test problems of the literature and large-scale randomly g enerated instances.