Volume 4, Issue 2, April 2015, Page: 35-39
Local Search Heuristic for Multiple Knapsack Problem
Balbal Samir, Computer science Department, USTOMB, Oran, Algeria
Laalaoui Yacine, IT Department, Taif University, Taif, Kingdom of Saudi Arabia
Benyettou Mohamed, Computer science Department, USTOMB, Oran, Algeria
Received: Dec. 2, 2014;       Accepted: Dec. 7, 2014;       Published: Feb. 16, 2015
DOI: 10.11648/j.ijiis.20150402.11      View  4242      Downloads  313
Abstract
In this paper we will present a heuristic method to solve the Multiple Knapsack Problem. The proposed method is an improvement of the IRT heuristic described in [2].the experimental study shows that our improvement leads some gain in time and solution quality against IRT, MTHM, Mulknap and ILOG CPLEX.
Keywords
Multiple Knapsack Problem, Local Search, Heuristic
To cite this article
Balbal Samir, Laalaoui Yacine, Benyettou Mohamed, Local Search Heuristic for Multiple Knapsack Problem, International Journal of Intelligent Information Systems. Vol. 4, No. 2, 2015, pp. 35-39. doi: 10.11648/j.ijiis.20150402.11
Reference
[1]
M. Lalami,M. Elkihel, D. Baz and V.Boyer, ”A procedure-based heuristic for 0-1 Multiple Knapsack Problems”, International Journal of Mathematics in Operational Research, vol. 4, No. 3, pp. 214-224, 2012.
[2]
Y. Laalaoui, “Improved Swap Heuristic for the Multiple Knapsack Problem” IWANN 2013, Part I, LNCS 7902, pp. 547–555, 2013.
[3]
S. Martello, P. Toth. “Knapsack problems: algorithms and computer implementations”. J Wiley. 1990.
[4]
J. Dréo, A. Petrowski, D. Taillard, P. Siarry"Métaheuristiques pour L'optimisation difficile" ,Eyrolles (Editions), November 2003
[5]
G. Ingargiola and J.F. Korsh, "An algorithm for the solution of 0-1 loading problems", Operations Research, 23(6):1110--1119, 1975.
[6]
M.S. Hung and J.C. Fisk, "An algorithm for the 0-1 multiple knapsack problem", Naval Research Logistics Quarterly, 571--579, 1978.
[7]
S. Martello and P. Toth., "Solution of the zero-one multiple knapsack problem", European Journal of Operational Research, 4, 1980.M. Young, The Technical Writer’s Handbook. Mill Valley, CA: University Science, 1989.
[8]
S. Martello and P. Toth., "A bound and bound algorithm for the zero-one multiple knapsack problem", Discrete Applied Mathematics, vol. 3, pp. 275--288, 1981.
[9]
D. Pisinger,"An exact algorithm for large multiple knapsack problems", European Journal of Operational Research, vol. 114, pp. 528--541, 1999.
[10]
A. Fukunaga, R.E Korf, "Bin Completion Algorithms for Multicontainer Packing, Knapsack, and Covering Problems", Journal of Artificial Intelligence Research, vol. 28, pp. 393--429, 2007.
[11]
A. Fukunaga, "A branch-and-bound algorithm for hard multiple knapsack problems", Annals of Operations Research, vol. 184, N. 1, pp. 97--119, 2011.
[12]
S. Martello and P. Toth., "Heuristic algorithms for the multiple knapsack problem", Computing, vol. 27, pp. 93--112, 1981.
[13]
M. Lalami,M. Elkihel, D. Baz and V .Boyer, "A procedure-based heuristic for 0-1 Multiple Knapsack Problems, International Journal of Mathematics in Operational Research, vol. 4, No. 3, pp. 214--224, 2012
[14]
E. Falkenauer, "A hybrid grouping genetic algorithm for bin packing", Journal of Heuristics, pages 2:5 - 30, 1996.
[15]
R. Raidl, "The multiple container packing problem: A genetic algorithm approach with weighted codings", ACM SIGAPP Applied Computing Review, pages 22 - 31, 1999.
[16]
A. Fukunaga., "A new grouping genetic algorithm for the multiple knapsack problem", In Proc. IEEE Congress on Evolutionary Computation, pages 2225--2232, 2008.
[17]
A. Fukunaga and Satoshi Tazoe, "Combining Multiple Representations in a Genetic Algorithm for the Multiple Knapsack Problem", In Proc of the 11th IEEE Congress on Evolutionary Computation, pages 2423 - 2430, 2009.
Browse journals by subject