| Peer-Reviewed

Local Search Heuristic for Multiple Knapsack Problem

Received: 2 December 2014     Accepted: 7 December 2014     Published: 16 February 2015
Views:       Downloads:
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.

Published in International Journal of Intelligent Information Systems (Volume 4, Issue 2)
DOI 10.11648/j.ijiis.20150402.11
Page(s) 35-39
Creative Commons

This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.

Copyright

Copyright © The Author(s), 2015. Published by Science Publishing Group

Keywords

Multiple Knapsack Problem, Local Search, Heuristic

References
[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.
Cite This Article
  • APA Style

    Balbal Samir, Laalaoui Yacine, Benyettou Mohamed. (2015). Local Search Heuristic for Multiple Knapsack Problem. International Journal of Intelligent Information Systems, 4(2), 35-39. https://doi.org/10.11648/j.ijiis.20150402.11

    Copy | Download

    ACS Style

    Balbal Samir; Laalaoui Yacine; Benyettou Mohamed. Local Search Heuristic for Multiple Knapsack Problem. Int. J. Intell. Inf. Syst. 2015, 4(2), 35-39. doi: 10.11648/j.ijiis.20150402.11

    Copy | Download

    AMA Style

    Balbal Samir, Laalaoui Yacine, Benyettou Mohamed. Local Search Heuristic for Multiple Knapsack Problem. Int J Intell Inf Syst. 2015;4(2):35-39. doi: 10.11648/j.ijiis.20150402.11

    Copy | Download

  • @article{10.11648/j.ijiis.20150402.11,
      author = {Balbal Samir and Laalaoui Yacine and Benyettou Mohamed},
      title = {Local Search Heuristic for Multiple Knapsack Problem},
      journal = {International Journal of Intelligent Information Systems},
      volume = {4},
      number = {2},
      pages = {35-39},
      doi = {10.11648/j.ijiis.20150402.11},
      url = {https://doi.org/10.11648/j.ijiis.20150402.11},
      eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ijiis.20150402.11},
      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.},
     year = {2015}
    }
    

    Copy | Download

  • TY  - JOUR
    T1  - Local Search Heuristic for Multiple Knapsack Problem
    AU  - Balbal Samir
    AU  - Laalaoui Yacine
    AU  - Benyettou Mohamed
    Y1  - 2015/02/16
    PY  - 2015
    N1  - https://doi.org/10.11648/j.ijiis.20150402.11
    DO  - 10.11648/j.ijiis.20150402.11
    T2  - International Journal of Intelligent Information Systems
    JF  - International Journal of Intelligent Information Systems
    JO  - International Journal of Intelligent Information Systems
    SP  - 35
    EP  - 39
    PB  - Science Publishing Group
    SN  - 2328-7683
    UR  - https://doi.org/10.11648/j.ijiis.20150402.11
    AB  - 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.
    VL  - 4
    IS  - 2
    ER  - 

    Copy | Download

Author Information
  • Computer science Department, USTOMB, Oran, Algeria

  • IT Department, Taif University, Taif, Kingdom of Saudi Arabia

  • Computer science Department, USTOMB, Oran, Algeria

  • Sections