Reduced costs propagation in an efficient implicit enumeration for the 01 multidimensional knapsack problem

DOI10.1007/s10878-007-9074-4zbMath1138.90014OpenAlexW2089131950MaRDI QIDQ2427438

Yannick Vimont, Sylvain Boussier, Michel Vasquez

Publication date: 13 May 2008

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-007-9074-4

zbMATH Keywords

Constraint propagationMultidimensional knapsack problemImplicit enumerationReduced costsVariable fixing

Mathematics Subject Classification ID

Boolean programming (90C09)

Related Items (20)

A ``reduce and solve approach for the multiple-choice multidimensional knapsack problem ⋮ Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems ⋮ Separation algorithms for 0-1 knapsack polytopes ⋮ Hybrid approaches for the two-scenario max-min knapsack problem ⋮ Solving large-scale multidimensional knapsack problems with a new binary harmony search algorithm ⋮ Improving problem reduction for 0-1 multidimensional knapsack problems with valid inequalities ⋮ Corrigendum to: ``Empirical orthogonal constraint generation for multidimensional 0/1 knapsack problems ⋮ A two-phase tabu-evolutionary algorithm for the 0-1 multidimensional knapsack problem ⋮ 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 ⋮ An iterative pseudo-gap enumeration approach for the multidimensional multiple-choice knapsack problem ⋮ Two-stage solution-based tabu search for the multidemand multidimensional knapsack problem ⋮ Improved core problem based heuristics for the 0/1 multi-dimensional knapsack problem ⋮ Iterative semi-continuous relaxation heuristics for the multiple-choice multidimensional knapsack problem ⋮ A heuristic approach for allocation of data to RFID tags: a data allocation knapsack problem (DAKP) ⋮ A multi-level search strategy for the 0-1 multidimensional knapsack problem ⋮ Kernel search: a general heuristic for the multi-dimensional knapsack problem ⋮ Empirical orthogonal constraint generation for multidimensional 0/1 knapsack problems ⋮ CORAL: An Exact Algorithm for the Multidimensional Knapsack Problem ⋮ Revisiting surrogate relaxation for the multidimensional knapsack problem

Uses Software

• OR-Library

Cites Work

• A genetic algorithm for the multidimensional knapsack problem
• An efficient preprocessing procedure for the multidimensional 0-1 knapsack problem
• The multidimensional 0-1 knapsack problem: an overview.
• Improved results on the 0--1 multidimensional knapsack problem
• Une approche hybride pour le sac à dos multidimensionnel en variables 0–1
• A Shrinking Boundary Algorithm for Discrete System Models

This page was built for publication: Reduced costs propagation in an efficient implicit enumeration for the 01 multidimensional knapsack problem