A Memetic Lagrangian Heuristic for the 0-1 Multidimensional Knapsack Problem
Joint Authors
Source
Discrete Dynamics in Nature and Society
Issue
Vol. 2013, Issue 2013 (31 Dec. 2013), pp.1-10, 10 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2013-05-16
Country of Publication
Egypt
No. of Pages
10
Main Subjects
Abstract EN
We present a new evolutionary algorithm to solve the 0-1 multidimensional knapsack problem.
We tackle the problem using duality concept, differently from traditional approaches.
Our method is based on Lagrangian relaxation.
Lagrange multipliers transform the problem, keeping the optimality as well as decreasing the complexity.
However, it is not easy to find Lagrange multipliers nearest to the capacity constraints of the problem.
Through empirical investigation of Lagrangian space, we can see the potentiality of using a memetic algorithm.
So we use a memetic algorithm to find the optimal Lagrange multipliers.
We show the efficiency of the proposed method by the experiments on well-known benchmark data.
American Psychological Association (APA)
Yoon, Yourim& Kim, Yong-Hyuk. 2013. A Memetic Lagrangian Heuristic for the 0-1 Multidimensional Knapsack Problem. Discrete Dynamics in Nature and Society،Vol. 2013, no. 2013, pp.1-10.
https://search.emarefa.net/detail/BIM-474464
Modern Language Association (MLA)
Yoon, Yourim& Kim, Yong-Hyuk. A Memetic Lagrangian Heuristic for the 0-1 Multidimensional Knapsack Problem. Discrete Dynamics in Nature and Society No. 2013 (2013), pp.1-10.
https://search.emarefa.net/detail/BIM-474464
American Medical Association (AMA)
Yoon, Yourim& Kim, Yong-Hyuk. A Memetic Lagrangian Heuristic for the 0-1 Multidimensional Knapsack Problem. Discrete Dynamics in Nature and Society. 2013. Vol. 2013, no. 2013, pp.1-10.
https://search.emarefa.net/detail/BIM-474464
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-474464