Heuristics for the 0-1 multidimensional knapsack problem

DOI10.1016/j.ejor.2007.06.068zbMath1176.90657OpenAlexW2102543230MaRDI QIDQ1042198

Didier El Baz, Moussa Elkihel, Vincent Boyer

Publication date: 7 December 2009

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2007.06.068

zbMATH Keywords

heuristicsbranch-and-cutsurrogate relaxationmultidimensional knapsack problemdynamic-programming

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Approximation methods and heuristics in mathematical programming (90C59) Dynamic programming (90C39)

Related Items (12)

An approximate algorithm for lexicographic search in multiple orders for the solution of the multidimensional Boolean knapsack problem ⋮ Surrogate upper bound sets for bi-objective bi-dimensional binary knapsack problems ⋮ Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems ⋮ Solving large-scale multidimensional knapsack problems with a new binary harmony search algorithm ⋮ Solving large 0-1 multidimensional knapsack problems by a new simplified binary artificial fish swarm algorithm ⋮ A theoretical and empirical investigation on the Lagrangian capacities of the \(0\)-\(1\) multidimensional knapsack problem ⋮ A memetic Lagrangian heuristic for the 0-1 multidimensional knapsack problem ⋮ Problem reduction heuristic for the \(0\)-\(1\) multidimensional knapsack problem ⋮ Solving knapsack problems on GPU ⋮ A hybrid algorithm for the unbounded knapsack problem ⋮ Revisiting surrogate relaxation for the multidimensional knapsack problem ⋮ Memory and Learning in Metaheuristics

Uses Software

• OR-Library
• Knapsack

Cites Work

• An exact search for the solution of the surrogate dual of the 0-1 bidimensional knapsack problem
• An efficient preprocessing procedure for the multidimensional 0-1 knapsack problem
• The multidimensional 0-1 knapsack problem: an overview.
• New trends in exact algorithms for the \(0-1\) knapsack problem
• Evolution and state-of-the-art in integer programming
• Cutting and surrogate constraint analysis for improved multidimensional knapsack solutions
• Load balancing methods and parallel dynamic programming algorithm using dominance technique applied to the 0-1 knapsack problem
• An Approximate Dynamic Programming Approach to Multidimensional Knapsack Problems
• Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimality
• Surrogate Constraints
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Heuristics for the 0-1 multidimensional knapsack problem