A Memetic Lagrangian Heuristic for the 0-1 Multidimensional Knapsack Problem
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 wel...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2013-01-01
|
| Series: | Discrete Dynamics in Nature and Society |
| Online Access: | http://dx.doi.org/10.1155/2013/474852 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832556227316416512 |
|---|---|
| author | Yourim Yoon Yong-Hyuk Kim |
| author_facet | Yourim Yoon Yong-Hyuk Kim |
| author_sort | Yourim Yoon |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-e2b51140f37041809cb5b918fb844cc7 |
| institution | Kabale University |
| issn | 1026-0226 1607-887X |
| language | English |
| publishDate | 2013-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Discrete Dynamics in Nature and Society |
| spelling | doaj-art-e2b51140f37041809cb5b918fb844cc72025-02-03T05:46:02ZengWileyDiscrete Dynamics in Nature and Society1026-02261607-887X2013-01-01201310.1155/2013/474852474852A Memetic Lagrangian Heuristic for the 0-1 Multidimensional Knapsack ProblemYourim Yoon0Yong-Hyuk Kim1Future IT R&D Laboratory, LG Electronics Umyeon R&D Campus, 38 Baumoe-ro, Seocho-gu, Seoul 137-724, Republic of KoreaDepartment of Computer Science and Engineering, Kwangwoon University, 20 Kwangwoon-ro, Nowon-gu, Seoul 139-701, Republic of KoreaWe 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.http://dx.doi.org/10.1155/2013/474852 |
| spellingShingle | Yourim Yoon Yong-Hyuk Kim A Memetic Lagrangian Heuristic for the 0-1 Multidimensional Knapsack Problem Discrete Dynamics in Nature and Society |
| title | A Memetic Lagrangian Heuristic for the 0-1 Multidimensional
Knapsack Problem |
| title_full | A Memetic Lagrangian Heuristic for the 0-1 Multidimensional
Knapsack Problem |
| title_fullStr | A Memetic Lagrangian Heuristic for the 0-1 Multidimensional
Knapsack Problem |
| title_full_unstemmed | A Memetic Lagrangian Heuristic for the 0-1 Multidimensional
Knapsack Problem |
| title_short | A Memetic Lagrangian Heuristic for the 0-1 Multidimensional
Knapsack Problem |
| title_sort | memetic lagrangian heuristic for the 0 1 multidimensional knapsack problem |
| url | http://dx.doi.org/10.1155/2013/474852 |
| work_keys_str_mv | AT yourimyoon amemeticlagrangianheuristicforthe01multidimensionalknapsackproblem AT yonghyukkim amemeticlagrangianheuristicforthe01multidimensionalknapsackproblem AT yourimyoon memeticlagrangianheuristicforthe01multidimensionalknapsackproblem AT yonghyukkim memeticlagrangianheuristicforthe01multidimensionalknapsackproblem |