A local search based heuristic for the demand constrained

We consider an extension of the 0-1 multidimensional knapsack problem in which there are greater-than-equal inequalities, called demand constraints, besides the standard less-than-equal constraints. Moreover the objective function coefficients are not constrained in sign. This problem is worth considering because it is embedded in the models of practical applications, because it has an intriguing combinatorial structure and because it appears to be a challenging problem for commercial ILP solvers. Our approach is based on a nested tabu search algorithm in which neighbourhoods of different structure are exploited. A first higher level tabu search is carried on in which both feasible and unfeasible regions are explored. In this diversification phase an oscillation method proceeds alternating between constructive and destructive steps. Occasionally, a lower level tabu search which implements an intensification strategy is applied. In this second phase only feasible solutions are analysed. The algorithm has been tested on a wide set of instances. Computational results are discussed.