Groupe d’études et de recherche en analyse des décisions

Adaptive Memory Search for Multidemand Multidimensional Knapsack Problems

Arne Løkketangen

We describe a simple adaptive memory search method for the 0/1 Multidemand Multidimensional Knapsack Problem (0/1 MDMKP). The search balances the level of infeasibility against the quality of the solution, and uses a simple dynamic tabu search mechanism. A weighting scheme to balance out the differences in the tightness of the constraints is also implemented. Computational results on a portfolio of test problems taken from the literature are reported, showing very favorable results, both in solution quality and in the ability of the search to find feasible solutions.