0-1 Multidimensional knapsack problem: Bounds on the sum of variables at optimum

Glover has been the first author to introduce an extra constraint, related to the sum of the variables fixed at 1 at the optimum, for solving 0-1 linear programming problems with implicit enumeration methods. In this paper, the authors propose a new algorithm to compute tight bounds of this sum for the 0-1 multidimensional knapsack problem. The method is based on the exact solution of the surrogate dual of relaxations which correspond to 0-1 bidimensional knapsack problems, and on the knowledge of a good primal feasible solution. Intensive numerical experiments show the efficiency of the present method over the classical test problems of literature, and large size instances with randomly generated data.