GPU Implementation of the Branch and Bound method for knapsack problems

Mohamed Esseghir Lalami, Didier El-Baz
CNRS, LAAS, 7 avenue du colonel Roche, F-31400 Toulouse, France
IEEE 26th International Parallel and Distributed Processing Symposium Workshops & PhD Forum, 2012


   title={GPU Implementation of the Branch and Bound method for knapsack problems},

   author={Lalami, M.E. and El-Baz, D.},



Download Download (PDF)   View View   Source Source   



In this paper, we propose an efficient implementation of the branch and bound method for knapsack problems on a CPU-GPU system via CUDA. Branch and bound computations can be carried out either on the CPU or on a GPU according to the size of the branch and bound list. A better management of GPUs memories, less GPUCPU communications and better synchronization between GPU threads are proposed in this new implementation in order to increase efficiency. Indeed, a series of computational results is displayed and analyzed showing a substantial speedup on a Tesla C2050 GPU.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: