A memetic Lagrangian heuristic for the 0-1 multidimensional knapsack problem
type: Item
instance of: scholarly article
title: A memetic Lagrangian heuristic for the 0-1 multidimensional knapsack problem
zbMATH Open document ID: 1264.90150
DOI: 10.1155/2013/474852
author: Yourim Yoon
author: Yong-Hyuk Kim
published in: Discrete Dynamics in Nature and Society
publication date: 2013-06-13T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C09
Mathematics Subject Classification ID: 90C59
zbMATH DE Number: 6175085
Wikidata QID: Q58921611
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1155/2013/474852
OpenAlex ID: W1976900421
cites work: Q4198056
cites work: CORAL: an exact algorithm for the multidimensional knapsack problem
cites work: An Exact Algorithm for the Two-Constraint 0–1 Knapsack Problem
cites work: A multi-level search strategy for the 0-1 multidimensional knapsack problem
cites work: Heuristics for the 0-1 multidimensional knapsack problem
cites work: A genetic algorithm for the multidimensional knapsack problem
cites work: Improved core problem based heuristics for the 0/1 multi-dimensional knapsack problem
cites work: Fast, effective heuristics for the 0-1 multi-dimensional knapsack problem
cites work: Improved convergent heuristics for the 0-1 multidimensional knapsack problem
cites work: A heuristic algorithm for the multidimensional zero-one knapsack problem
cites work: Improved results on the 0--1 multidimensional knapsack problem
cites work: Reduced costs propagation in an efficient implicit enumeration for the 01 multidimensional knapsack problem
cites work: A theoretical and empirical investigation on the Lagrangian capacities of the \(0\)-\(1\) multidimensional knapsack problem
cites work: Evolutionary algorithms for constrained optimization problems
cites work: Some Experiences On Solving Multiconstraint Zero-One Knapsack Problems With Genetic Algorithms
cites work: The multidimensional 0-1 knapsack problem: an overview.
cites work: The multidimensional 0-1 knapsack problem -- bounds and computational aspects
cites work: Q4821303
cites work: Q3328287
cites work: A new adaptive multi-start technique for combinatorial global optimizations
cites work: The multidimensional knapsack problem: structure and algorithms
cites work: Obtaining test problems via Internet
cites work: A theoretical and empirical study on unbiased boundary-extended crossover for real-valued representation
description: scientific article; zbMATH DE number 6175085