Article ID: | iaor20072551 |
Country: | United Kingdom |
Volume: | 33 |
Issue: | 9 |
Start Page Number: | 2508 |
End Page Number: | 2525 |
Publication Date: | Sep 2006 |
Journal: | Computers and Operations Research |
Authors: | Lkketangen Arne, Arntzen Halvard, Hvattum Lars M. |
Keywords: | programming: integer |
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 terms of solution quality and the ability of the search to find feasible solutions.