Improved results on the 0--1 multidimensional knapsack problem

DOI10.1016/j.ejor.2004.01.024zbMath1112.90366OpenAlexW2095018715MaRDI QIDQ1776956

Michel Vasquez, Yannick Vimont

Publication date: 12 May 2005

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

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

zbMATH Keywords

linear programmingheuristicstabu searchvariables fixing

Mathematics Subject Classification ID

Integer programming (90C10) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Boolean programming (90C09)

Related Items (43)

An approximate algorithm for lexicographic search in multiple orders for the solution of the multidimensional Boolean knapsack problem ⋮ A ``reduce and solve approach for the multiple-choice multidimensional knapsack problem ⋮ New convergent heuristics for 0-1 mixed integer programming ⋮ Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems ⋮ Improving problem reduction for 0-1 multidimensional knapsack problems with valid inequalities ⋮ Optimal allocation of stock levels and stochastic customer demands to a capacitated resource ⋮ Corrigendum to: ``Empirical orthogonal constraint generation for multidimensional 0/1 knapsack problems ⋮ Combining (Integer) Linear Programming Techniques and Metaheuristics for Combinatorial Optimization ⋮ Solving large 0-1 multidimensional knapsack problems by a new simplified binary artificial fish swarm algorithm ⋮ A new discrete electromagnetism-based meta-heuristic for solving the multidimensional knapsack problem using genetic operators ⋮ A two-phase tabu-evolutionary algorithm for the 0-1 multidimensional knapsack problem ⋮ Reduced costs propagation in an efficient implicit enumeration for the 01 multidimensional knapsack problem ⋮ A theoretical and empirical investigation on the Lagrangian capacities of the \(0\)-\(1\) multidimensional knapsack problem ⋮ Intelligent water drops algorithm ⋮ A memetic Lagrangian heuristic for the 0-1 multidimensional knapsack problem ⋮ Modeling multiple plant sourcing decisions ⋮ Second-order cover inequalities ⋮ Scatter search for the 0-1 multidimensional knapsack problem ⋮ A hybrid quantum inspired harmony search algorithm for 0-1 optimization problems ⋮ Essential particle swarm optimization queen with tabu search for MKP resolution ⋮ Approximate and exact merging of knapsack constraints with cover inequalities ⋮ Higher-order cover cuts from zero-one knapsack constraints augmented by two-sided bounding inequalities ⋮ Bringing order into the neighborhoods: Relaxation guided variable neighborhood search ⋮ Particle swarm optimization with time-varying acceleration coefficients for the multidimensional knapsack problem ⋮ Two-stage solution-based tabu search for the multidemand multidimensional knapsack problem ⋮ Fast, effective heuristics for the 0-1 multi-dimensional knapsack problem ⋮ Improved core problem based heuristics for the 0/1 multi-dimensional knapsack problem ⋮ Greedy algorithms for a class of knapsack problems with binary weights ⋮ A multi-level search strategy for the 0-1 multidimensional knapsack problem ⋮ Improved convergent heuristics for the 0-1 multidimensional knapsack problem ⋮ Identifying redundancy in multi-dimensional knapsack constraints based on surrogate constraints ⋮ Alternating control tree search for knapsack/covering problems ⋮ Kernel search: a general heuristic for the multi-dimensional knapsack problem ⋮ A software framework for fast prototyping of meta‐heuristics hybridization ⋮ A binary differential search algorithm for the 0-1 multidimensional knapsack problem ⋮ Empirical orthogonal constraint generation for multidimensional 0/1 knapsack problems ⋮ A Partheno-Genetic Algorithm for Dynamic 0-1 Multidimensional Knapsack Problem ⋮ A hybrid of nested partition, binary ant system, and linear programming for the multidimensional knapsack problem ⋮ Matheuristic for the decentralized factories scheduling problem ⋮ Algorithmic aspects for power-efficient hardware/software partitioning ⋮ CORAL: An Exact Algorithm for the Multidimensional Knapsack Problem ⋮ An iterative variable-based fixation heuristic for the 0-1 multidimensional knapsack problem ⋮ Advanced greedy algorithms and surrogate constraint methods for linear and quadratic knapsack and covering problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A simulated annealing approach to the multiconstraint zero-one knapsack problem
• A genetic algorithm for the multidimensional knapsack problem
• An efficient preprocessing procedure for the multidimensional 0-1 knapsack problem
• An efficient tabu search approach for the 0-1 multidimensional knapsack problem
• Cutting and surrogate constraint analysis for improved multidimensional knapsack solutions
• Dynamic tabu list management using the reverse elimination method
• The Effects of Coefficient Correlation Structure in Two-Dimensional Knapsack Problems on Solution Procedure Performance
• Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimality
• Pivot and Complement–A Heuristic for 0-1 Programming
• Tabu Search—Part II
• A Branch and Bound Method for the Multiconstraint Zero-One Knapsack Problem
• Sac à dos multidimensionnel en variables 0-1 : encadrement de la somme des variables à l'optimum
• Une approche hybride pour le sac à dos multidimensionnel en variables 0–1

This page was built for publication: Improved results on the 0--1 multidimensional knapsack problem