Solving knapsack problems on GPU

DOI10.1016/j.cor.2011.03.014zbMath1251.90014OpenAlexW1987169484MaRDI QIDQ1761942

Vincent Boyer, Moussa Elkihel, Didier El Baz

Publication date: 15 November 2012

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

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

zbMATH Keywords

parallel computingcombinatorial optimization problemsCUDAGPU computingdense dynamic programming

Mathematics Subject Classification ID

Applications of mathematical programming (90C90) Combinatorial optimization (90C27) Dynamic programming (90C39) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items (8)

Dual mean field search for large scale linear and quadratic knapsack problems ⋮ Optimizing energy consumption of robotic cells by a branch \& bound algorithm ⋮ A novel approach for nurse rerostering based on a parallel algorithm ⋮ A low-space algorithm for the subset-sum problem on GPU ⋮ Parallel computational optimization in operations research: a new integrative framework, literature review and research directions ⋮ Accelerating exact and approximate inference for (distributed) discrete optimization with GPUs ⋮ Route relaxations on GPU for vehicle routing problems ⋮ Using GPU Computing for Solving the Two-Dimensional Guillotine Cutting Problem

Uses Software

• CUDA
• Knapsack

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Heuristics for the 0-1 multidimensional knapsack problem
• Experiments with parallel algorithms for combinatorial problems
• The two list algorithm for the knapsack problem on an FPS T20
• Dynamic programming algorithms for the zero-one knapsack problem
• A parallel two-list algorithm for the knapsack problem
• New trends in exact algorithms for the \(0-1\) knapsack problem
• A procedure-based heuristic for 0-1 multiple knapsack problems
• Load balancing methods and parallel dynamic programming algorithm using dominance technique applied to the 0-1 knapsack problem
• A Survey Of Parallel Algorithms For One-Dimensional Integer Knapsack Problems

This page was built for publication: Solving knapsack problems on GPU