Abstract
In this paper, we approximately solve the multiple-choice multi-dimensional knapsack problem. We propose an algorithm which is based upon reactive local search and where an explicit check for the repetition of configurations is added to the local search. The algorithm starts by an initial solution and improved by using a fast iterative procedure. Later, both deblocking and degrading procedures are introduced in order (i) to escape to local optima and, (ii) to introduce diversification in the search space. Finally, a memory list is applied in order to forbid the repetition of configurations. The performance of the proposed approaches has been evaluated on several problem instances. Encouraging results have been obtained.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
E. Balas and E. Zemel, “An algorithm for large zero-one knapsack problem,” Operations Research, vol. 28, pp. 1130–1154, 1980.
P. Chu and J.E. Beasley, “A genetic algorithm for the multidimensional knapsack problem,” Journal of Heuristics, vol. 4, pp. 63–86, 1998.
J.E. Beasley and P.C. Chu, “A genetic algorithm for the set covering problem,” Europ. J. Opl. Res, vol. 94, pp. 392–404, 1996.
D. Fayard and G. Plateau, “An algorithm for the solution of the 0-1 knapsack problem,” Computing, vol. 28, pp. 269–287, 1982.
M. Hifi, M. Michrafy and A. Sbihi, “Heuristic algorithms for the multiple-choice multidimensional knapsack problem,” Journal of the Operational Research Society, vol. 55, pp. 1323–1332, 2004.
H. Kellerer, U. Pferschy, and D. Pisinger, Knapsack Problems, Springer, 2003.
S. Khan, K.F. Li, E.G. Manning, and MD. M. Akbar, “Solving the knapsack problem for adaptive multimedia systems,” Studia Informatica, an International Journal, Special Issue on Cutting, Packing and Knapsacking Problems, vol. 2, no. 1, pp. 154–174, 2002.
S. Khan, “Quality adaptation in a multi-session adaptive multimedia system: Model and architecture,” PhD Thesis, Department of Electronical and Computer Engineering, Uiversity of Victoria, May 1998.
H. Luss, “Minmax resource allocation problems: Optimization and parametric analysis,” European Journal of Operational Research, vol. 60, pp. 76–86, 1992.
S. Martello, D. Pisinger, and P. Toth, “Dynamic programming and strong bounds for the 0-1 knapsack problem,” Management Science, vol. 45, pp. 414–424, 1999.
M. Moser, D.P. Jokanović, and N. Shiratori, “An algorithm for the multidimesional multiple-choice knapsack problem,” IEECE Transactions on Fundamentals of Electronics, vol. 80, no. 3, pp. 582–589, 1997.
J.S. Pang and C.S. Yu, “A min-max resource allocation problem with substitutions,” European Journal of Operational Research, vol. 41, pp. 218–223, 1989.
D. Pisinger, “A minimal algorithm for the 0-1 knapsack problem,” Operations Research, vol. 45, pp. 758–767, 1997.
D. Pisinger, “A minimal algorithm for the Multiple-choice Knapsack Problem,” European Journal of Operational Research, vol. 83, pp. 394–410, 1995.
J. Richardson, M. Palmer, G. Liepins, and M. Hilliard, “Some guidelines for genetic algorithms with penalty functions,” in Proceedings of the Third International Conference on Genetic Algorithms, Schaffer J (Eds.), Maurgan Kaufmann, 1989 pp. 191–197.
Y. Toyoda, “A simplified algorithm for obtaining approximate solution to zero-one programming problems,” Management Science, vol. 21, pp. 1417–1427, 1975.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Hifi, M., Michrafy, M. & Sbihi, A. A Reactive Local Search-Based Algorithm for the Multiple-Choice Multi-Dimensional Knapsack Problem. Comput Optim Applic 33, 271–285 (2006). https://doi.org/10.1007/s10589-005-3057-0
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10589-005-3057-0