We apologize for a recent technical issue with our email system, which temporarily affected account activations. Accounts have now been activated. Authors may proceed with paper submissions. PhDFocusTM
CFP last date
20 December 2024
Call for Paper
January Edition
IJCA solicits high quality original research papers for the upcoming January edition of the journal. The last date of research paper submission is 20 December 2024

Submit your paper
Know more
The week's pick
Responsive image
Improved Shuffled Frog Leaping Algorithm with Self-Adaptive Shuffling for Fuzzy Logic PD+G Controller Optimization in Robotic Manipulators

Duc Hoang Nguyen
Random Articles
Reseach Article

Smart Agents for the Multidimensional Multi-choice Knapsack Problem

by Skander Htiouech, Ameur Alzaidi
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 174 - Number 6
Year of Publication: 2017
Authors: Skander Htiouech, Ameur Alzaidi
10.5120/ijca2017915404

Skander Htiouech, Ameur Alzaidi . Smart Agents for the Multidimensional Multi-choice Knapsack Problem. International Journal of Computer Applications. 174, 6 ( Sep 2017), 5-9. DOI=10.5120/ijca2017915404

@article{ 10.5120/ijca2017915404,
author = { Skander Htiouech, Ameur Alzaidi },
title = { Smart Agents for the Multidimensional Multi-choice Knapsack Problem },
journal = { International Journal of Computer Applications },
issue_date = { Sep 2017 },
volume = { 174 },
number = { 6 },
month = { Sep },
year = { 2017 },
issn = { 0975-8887 },
pages = { 5-9 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume174/number6/28409-2017915404/ },
doi = { 10.5120/ijca2017915404 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-07T00:21:24.966541+05:30
%A Skander Htiouech
%A Ameur Alzaidi
%T Smart Agents for the Multidimensional Multi-choice Knapsack Problem
%J International Journal of Computer Applications
%@ 0975-8887
%V 174
%N 6
%P 5-9
%D 2017
%I Foundation of Computer Science (FCS), NY, USA
Abstract

In this paper, we propose a multi-agent approach for solving the multidimensional multi-choice knapsack problem (called MMKP). The MMKP is an NP-Hard optimization problem in strong sense. It is considered as a combination of two other variants such as: the multi-choice knapsack problem (MCKP) and the multidimensional knapsack problem (MDKP). The MMKP can be applied in many problems in real world. It can model many industrial situations, such as capital budgeting, model of allocation resources and finance. The particular properties of the MMKP favor its decomposition into many MMKP sub-problems with small sizes. The assignment of sub-problems and the sharing of available resources are allocated to a first agent. Each subproblem is then solved by an agent. To work collaboratively, a strategic negotiation between agents has been defined. A coordinator agent (CA) will evaluate and merge the generated solutions to build a feasible solution to the initial problem. The choice rules of the CA is modeled as a multidimensional knapsack problem (MKP). The proposed method is able to solve several instances of literature effectively, in particular for large size instances.

References
  1. Glover F, Laguna M. Tabu search. Boston: Kluwer Academic Publishers; (1998).
  2. Glover F, GA.Kochenberger. ”Critical event tabu search for multidimensional knapsack problems”. In: Osman IH, Kelly JP, editors. Metaheuristics: theory and applications. p. 407-27. (1996)
  3. Hanafi S, Freville A. An efficient tabu search approach for the 0-1 multidimensional knapsack problem. European Journal of Operational Research (1998).
  4. Moser M, Declarative scheduling for optimally graceful QoS degradation, in Proc. IEEE Int. Conf. Multimedia Computing Systems (ICMCS), pp. 86 93(1996).
  5. L. Chen, The utility model applied to layer-coded sources, Dept. of Computer Science, University of Victoria, Victoria, BC, Canada, (1998).
  6. Khan S, Quality adaptation in a multisession multimedia system : Model, algorithms and architecture, Ph.D. dissertation, Department of Electrical and Computer Engineering, University of Victoria, Canada 1998.
  7. Khan S, K. F. Li and E.G. Manning. The Utility Model for Adaptive Multimedia System. In International Workshop on Multimedia Modeling, pages 111-126 (1997).
  8. Garey MR, Johnson DS. Computers and intractability: a guide to the theory of NP completeness. San Francisco: Freeman; (1979).
  9. Martello S, Toth P. Knapsack problems. New York: Wiley; (1990).
  10. Healy Jr. WC. Multiple choice programming. Operations Research; 12:122. (1964)
  11. Lin EYH. Multiple choice programming: a state-ofthe- art review. International Transactions in Operational Research;1:409-421. (1994)
  12. Lin EYH. A bibliographical survey on some well-known nonstandard knapsack problems.;36(4): 274 317 INFOR (1998).
  13. Htiouech. S, Sadok Bouamama and Rabeh Attia: Using surrogate information to solve the multidimensional multi-choice knapsack problem. IEEE Congress on Evolutionary Computation 2013: 2102-2107
  14. Peterson CC. Computational experience with variants of the Balas algorithm applied to the selection of research and development projects. Management Science 13:736 50.(1967)
  15. Chu PC, Beasley JE. A genetic algorithm for the multidimensional knapsack problem. Journal of Heuristics;4: 686. (1998)
  16. Bertsimas D, Demir R. An approximate dynamic programming approach to multidimensional knapsack problems. Management Science;48(4):550-65 (2002)
  17. Mhand Hifi, Slim Sadfi, Abdelkader Sbihi. ”An exact algorithm for the multiple-choice multidimensional knapsack problem”. Cahiers de la MSE b04024, Maison des Sciences Economiques, University paris pantheon-Sorbonne. (2004)
  18. Parra-Hemendez R, N.Dimopoulos. ”A New Heuristic for Solving the Multi-choice Multidimensional knapsack problem”. Systems, Man and Cybernetics, Part A: Systems and Humans, IEEE Transactions. Volume: 35 , Issue: 5 Page(s): 708- 717 (2005)
  19. Kellerer H, Pferschy U, Pisinger D. Knapsack problems. Berlin: Springer; 2004.
  20. Chaitr S. Hiremath, Raymond R. Hill2. New greedy heuristics for the Multiple-choice Multi-dimensional Knapsack Problem. International Journal of Operational Research Volume 2, 2007 Pages 495-512.
  21. Shahrear Iqbal, Md. Faizul Bari, M. Sohel Rahman: Solving the Multi-dimensional Multi-choice Knapsack Problem with the Help of Ants. ANTS Conference 2010: 312-323
  22. Alaya I, C. Solnon et K. Ghedira. Des fourmis pour le sac- -dos multidimensionnel. Dans : 4mes Journes Francophones de Recherche Oprationnelle (Francoro 2004), Fribourg, Suisse, pp. 159-160.
  23. Sbihi A, A best first search exact algorithm for the multiplechoice multidimensional knapsack problem, Journal of Combinatorial Optimization 13 (4) (2007) 337-351.
  24. N. Cherfi and M. Hifi. Hybrid algorithms for the multiplechoice multi-dimensional knapsack problem. International Journal of Operational Research, 5(1):89-109, 2009.
  25. Raid Mansi, Claudio Alves, J. M. Valerio de Carvalho and Said Hanafi. A hybrid heuristic for the multiple choice multidimensional knapsack problem. Engineering Optimization, 2012. DOI:10.1080/0305215X.2012.717072.
  26. Htiouech. S, S. Bouamama, and R. Attia. 2013. ”OSC: Solving the Multidimensional Multi-Choice Knapsack Problem with Tight Strategic Oscillation Using Surrogate Constraints”. International Journal of Computer Applications 73. (13): 1-22.
  27. S.Htiouech, S.Bouamama, A Lagrangian and Surrogate information enhanced tabu search for the MMKP. 2014 IEEEWorld Congress on Computational Intelligence. IEEE WCCI. July 6- 11, 1461-1468, Beijing, China.
  28. M. Ben Rejeb, S. Htiouech, and S. Bouamama, ” A CPU-GPU Parallel Approach to Solve Multiple Choice Multidimensional Knapsack Problem” Proceedings of META-2016 : 6th International Conference on Metaheuristics and Nature Inspired computing. P154-156
  29. H. Pirkul. Efficient algorithms for the capacitated concentrator location problem. Computers and Operations Research, 14(3) :197-208, 1987.
  30. M. Akbar, O. Ergun, and A. Punnen. Heuristic solutions for the multiplechoice multi-dimensional knapsack problem. In International Conference on Computer Science, San Francisco, USA, 2001.
  31. Mansi, R., C. Alves, J. M. Valerio de Carvalho, and S. Hanafi. 2013. A Hybrid Heuristic for the Multiple Choice Multidimensional Knapsack Problem. Engineering Optimization 45 (8): 983-1004.
  32. H Shojaei, TH Wu, A Davoodi, and T Basten, ”A paretoalgebraic framework for signal power optimization in global routing,” in Proceedings of the 16th ACM/IEEE international symposium on Low power electronics and design, Austin, Texas, USA, 2010, pp. 407 - 412.
  33. Stefan Vo, Eduardo Lalla-Ruiz (2016) A set partitioning reformulation for the multiple-choice multidimensional knapsack problem, Engineering Optimization, 48:5, 831-850, DOI: 10.1080/0305215X.2015.1062094
  34. Shanping Qiao, Ling Zhao, Yongzheng Lin . Shixian Wang. A Distributed Algorithm for 0-1 Knapsack Problem Based on Mobile Agent. Intelligent Systems Design and Applications, 2008. ISDA ’08. Eighth International Conference on. DOI: 10.1109/ISDA.2008.110. Nov 2008.
  35. Brent A. Smolinski. Approximating the 0-1 Multiple Knapsack Problem with Agent Decomposition and Market Negotiation. International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems IEA/AIE 2000: Intelligent Problem Solving. Methodologies and Approaches p 296-306.
  36. Chen, Y., and J.-K. Hao. 2014. A Reduce and Solve Approach for the Multiple-Choice Multidimensional Knapsack Problem. European Journal of Operational Research 239 (2): 313-322.
  37. J. ferber, Multi-agent systems : an Introduction to distributed artificial intelligence, new York: addison-wesley, 1999.
  38. J.Liu, H. jing, Y.Y . Tang. Multi-agent oriented constraint satisfaction, Artificial Intelligence, Vol. 136, No.1, 101-144 2002.
  39. J Han, J Pei, andMKamber, Data mining : concepts and techniques.: Burlington : Elsevier Science, 2011.
  40. CS Hiremath and RR Hill, ”First-level tabu search approach for solving the multiple-choice multidimensional knapsack problem,” International Journal of Metaheuristics, vol. 2, pp. 174-199, 2013.
  41. Y Xia, C Gao, and JL Li, ”A Stochastic Local Search Heuristic for the Multidimensional Multiple-choice Knapsack Problem,” Communications in Computer and Information Science, vol. 562, pp. 513-522, December 2015.
Index Terms

Computer Science
Information Sciences

Keywords

Combinatorial optimization Agents multiple choice knapsack problem

Powered by PhDFocusTM