Hard multidimensional multiple choice knapsack problems, an empirical study

DOI10.1016/j.cor.2009.04.006zbMath1178.90288OpenAlexW2116220526MaRDI QIDQ733540

Gwendal Simon, Bing Han, Jimmy Leblet

Publication date: 16 October 2009

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2009.04.006

zbMATH Keywords

algorithmperformance evaluationknapsack problemmultidimensionalmultiple choice

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items (max. 100)

Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems ⋮ Solving constrained optimization problems by solution-based decomposition search ⋮ A fuzzy multidimensional multiple-choice knapsack model for project portfolio selection using an evolutionary algorithm ⋮ A trust region method for the solution of the surrogate dual in integer programming ⋮ A decomposition approach for multidimensional knapsacks with family‐split penalties ⋮ Piece selection algorithms for layered video streaming in P2P networks ⋮ Approximation schemes for deal splitting and covering integer programs with multiplicity constraints ⋮ Iterative semi-continuous relaxation heuristics for the multiple-choice multidimensional knapsack problem ⋮ A Decentralized Heuristic for Multiple-Choice Combinatorial Optimization Problems ⋮ A multi-criteria approach to approximate solution of multiple-choice knapsack problem ⋮ The multiple multidimensional knapsack with family-split penalties ⋮ SAT encodings for pseudo-Boolean constraints together with at-most-one constraints

Uses Software

• CPLEX
• GLPK
• Knapsack

Cites Work

• Unnamed Item
• Unnamed Item
• Packing and partitioning orbitopes
• A column generation method for the multiple-choice multi-dimensional knapsack problem
• Exploiting orbits in symmetric ILP
• Where are the hard knapsack problems?
• A best first search exact algorithm for the multiple-choice multidimensional knapsack problem
• Solving the multidimensional multiple-choice knapsack problem by constructing convex hulls
• A reactive local search-based algorithm for the multiple-choice multi-dimensional knapsack problem
• Core Problems in Knapsack Algorithms
• MVRC Heuristic for Solving the Multi-Choice Multi-Constraint Knapsack Problem
• The knapsack problem: A survey
• Heuristic algorithms for the multiple-choice multidimensional knapsack problem
• Orbitopal Fixing

This page was built for publication: Hard multidimensional multiple choice knapsack problems, an empirical study