AN EXACT ALGORITHM FOR THE 0-1-COLLAPSING KNAPSACK-PROBLEM

An exact algorithm is proposed for the 0-1 collapsing knapsack problem as defined by Guignard and Posner. Bounding of the number of variable s equal to 1 in an optimal solution is extensively used, as well as in ner- and outer-linearization of the nonlinear right-hand side of the c onstraint. This allows generally a drastic reduction of the feasible d omain. An implicit enumeration scheme solves the problem reduced by th e preprocessing phase. Computational experiments are reported on.