Reduced costs propagation in an efficient implicit enumeration for the 0–1 multidimensional knapsack problem

In a previous work we proposed a variable fixing heuristics for the 0–1 Multidimensional knapsack problem. This approach uses fractional optima calculated in hyperplanes which contain the binary optimum. This algorithm obtained best lower bounds on the or-library benchmarks. Although it is very attractive in terms of results, this method does not prove the optimality of the solutions found and may fix variables to a non-optimal value. In this paper, we propose an implicit enumeration based on a reduced costs analysis which tends to fix non-basic variables to their exact values.