Name
Title | ||
|---|---|---|
A theoretical and empirical investigation on the Lagrangian capacities of the 0-1 multidimensional knapsack problem. |
Abstract | ||
|---|---|---|
We present a novel Lagrangian method to find good feasible solutions in theoretical and empirical aspects. After investigating the concept of Lagrangian capacity, which is the value of the capacity constraint that Lagrangian relaxation can find an optimal solution, we formally reintroduce Lagrangian capacity suitable to the 0-1 multidimensional knapsack problem and present its new geometric equivalent condition including a new associated property. Based on the property, we propose a new Lagrangian heuristic that finds high-quality feasible solutions of the 0-1 multidimensional knapsack problem. We verify the advantage of the proposed heuristic by experiments. We make comparisons with existing Lagrangian approaches on benchmark data and show that the proposed method performs well on large-scale data. (C) 2011 Elsevier B.V. All rights reserved. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1016/j.ejor.2011.11.011 | European Journal of Operational Research |
Keywords | Field | DocType |
Integer programming,0-1 Multidimensional knapsack problem,Lagrangian method,Lagrangian capacity | Heuristic,Mathematical optimization,Lagrangian,Change-making problem,Lagrangian heuristic,Continuous knapsack problem,Integer programming,Lagrangian relaxation,Knapsack problem,Mathematics | Journal |
Volume | Issue | ISSN |
218 | 2 | 0377-2217 |
Citations | PageRank | References |
3 | 0.42 | 43 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yourim Yoon | 1 | 185 | 17.18 |
| Yong-Hyuk Kim | 2 | 355 | 40.27 |
| Byung Ro Moon | 3 | 366 | 31.12 |