A memetic Lagrangian heuristic for the 0-1 multidimensional knapsack problem (Q1956060)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A memetic Lagrangian heuristic for the 0-1 multidimensional knapsack problem |
scientific article |
Statements
A memetic Lagrangian heuristic for the 0-1 multidimensional knapsack problem (English)
0 references
13 June 2013
0 references
Summary: 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.
0 references
0 references
0 references