Solving the multidimensional multiple-choice knapsack problem by constructing convex hulls

DOI10.1016/j.cor.2004.09.016zbMath1104.90039OpenAlexW2006738678MaRDI QIDQ2496024

Eric G. Manning, Gholamali C. Shoja, M. Sohel Rahman, Md Mostofa Akbar, Mohammad Kaykobad

Publication date: 30 June 2006

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

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

zbMATH Keywords

algorithmsheuristicsconvex hullmultimedia systemsMMKP

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items

Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems ⋮ Vehicle routing problems with alternative paths: an application to on-demand transportation ⋮ Combining local branching and descent method for solving the multiple‐choice knapsack problem with setups ⋮ Vector bin packing with multiple-choice ⋮ An exact algorithm for bilevel 0-1 knapsack problems ⋮ Two-dimensional knapsack-block packing problem ⋮ A two-phase kernel search variant for the multidimensional multiple-choice knapsack problem ⋮ Solving the multidimensional knapsack problems with generalized upper bound constraints by the adaptive memory projection method ⋮ A heuristic approach for allocation of data to RFID tags: a data allocation knapsack problem (DAKP) ⋮ Adaptive large neighborhood search for solving the circle bin packing problem ⋮ A multi-criteria approach to approximate solution of multiple-choice knapsack problem ⋮ Hard multidimensional multiple choice knapsack problems, an empirical study ⋮ An Exact Algorithm for the Multiple-Choice Multidimensional Knapsack Based on the Core

Uses Software

• Knapsack

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A heuristic algorithm for the multidimensional zero-one knapsack problem
• A simulated annealing approach to the multiconstraint zero-one knapsack problem
• The 0-1 knapsack problem with multiple choice constraints
• New trends in exact algorithms for the \(0-1\) knapsack problem
• Dynamic tabu list management using the reverse elimination method
• A Simplified Algorithm for Obtaining Approximate Solutions to Zero-One Programming Problems
• A Branch and Bound Method for the Multiconstraint Zero-One Knapsack Problem