Improved results on the 0–1 multidimensional knapsack problem

Geometric constraint and cutting planes have been successfully used to solve the 0–1 multidimensional knapsack problem. Our algorithm combines Linear Programming with an efficient tabu search. It gives best results when compared with other algorithms on benchmarks issued from the OR-Library. Embedding this algorithm in a variables fixing heuristic still improves our previous results. Furthermore difficult subproblems with about 100 variables issued from the 500 original ones could be generated. These small subproblems are always very hard to solve.