Local Search Heuristic for Multiple Knapsack Problem

Balbal Samir; Laalaoui Yacine; Benyettou Mohamed

doi:doi:10.11648/j.ijiis.20150402.11

| Peer-Reviewed

Local Search Heuristic for Multiple Knapsack Problem

Balbal Samir, Laalaoui Yacine, Benyettou Mohamed

Published in International Journal of Intelligent Information Systems (Volume 4, Issue 2)

Received: 2 December 2014 Accepted: 7 December 2014 Published: 16 February 2015

Views: Downloads:

Download PDF

Share This Article

Twitter
Linked In
Facebook

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

Plain Text BibTeX RIS

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

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

Download PDF

Sections

Plain Text BibTeX RIS

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