Solving knapsack problems on GPU

DOI10.1016/J.COR.2011.03.014MaRDI QIDQ1761942zbMATH OpenOpenAlexFDO

Authors Vincent Boyer, Didier El Baz, Moussa Elkihel

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 computingCUDAcombinatorial optimization problemsGPU 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)

Recommendations

• A parallel two-list algorithm for the knapsack problem
• A combined parallel algorithm for solving the knapsack problem
• Parallel Algorithms for Knapsack Type Problems
• A low-space algorithm for the subset-sum problem on GPU
• An efficient parallel algorithm for solving the knapsack problem on hypercubes

Cites work

• scientific article; zbMATH DE number 3126094 (Why is no real title available?)
• scientific article; zbMATH DE number 44282 (Why is no real title available?)
• scientific article; zbMATH DE number 2107164 (Why is no real title available?)
• A Survey Of Parallel Algorithms For One-Dimensional Integer Knapsack Problems
• A parallel two-list algorithm for the knapsack problem
• A procedure-based heuristic for 0-1 multiple knapsack problems
• Dynamic programming algorithms for the zero-one knapsack problem
• Experiments with parallel algorithms for combinatorial problems
• Heuristics for the 0-1 multidimensional knapsack problem
• Load balancing methods and parallel dynamic programming algorithm using dominance technique applied to the 0-1 knapsack problem
• New trends in exact algorithms for the \(0-1\) knapsack problem
• The two list algorithm for the knapsack problem on an FPS T20

Cited in

(11)

• scientific article; zbMATH DE number 1863309 (Why is no real title available?)
• GPU-based acceleration of system-level design tasks
• A low-space algorithm for the subset-sum problem on GPU
• A novel approach for nurse rerostering based on a parallel algorithm
• Using GPU computing for solving the two-dimensional guillotine cutting problem
• Dual mean field search for large scale linear and quadratic knapsack problems
• Parallel implementation of an exact two-phase method for the biobjective knapsack problem
• Optimizing energy consumption of robotic cells by a branch \& bound algorithm
• 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

Describes a project that uses

Uses Software

• Knapsack
• CUDA

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1761942)