An exact algorithm for the 0–1 collapsing knapsack problem

AbstractAn exact algorithm is proposed for the 0–1 collapsing knapsack problem as defined by Guignard and Posner. Bounding of the number of variables equal to 1 in an optimal solution is extensively used, as well as inner- and outer-linearization of the nonlinear right-hand side of the constraint. This allows generally a drastic reduction of the feasible domain. An implicit enumeration scheme solves the problem reduced by the preprocessing phase. Computational experiments are reported on