Browsing by Author "Chekini, Mehdi"

Filter results by typing the first few letters
Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    Parallel B&B Algorithm on Hybrid Multicore/GPU Architecture
    (IEEE, 2013-11-15) Bendjoudi, Ahcène; Chekini, Mehdi; Gharbi, Makhlouf; Mehdi, Malika; Benatchba, Karima; Sitayeb-Benbouzid, Fatima; Melab, Nouredine
    B&B algorithms are well known techniques for exact solving of combinatorial optimization problems (COP). They perform an implicit enumeration of the search space instead of exhaustive one. Based on a pruning technique, they reduce considerably the computation time required to explore the whole search space. Nevertheless, these algorithms remain inefficient when dealing with large combinatorial optimization instances. They are time-intensive and they require a huge computing power to be solved optimally. Nowadays, multi-core-based processors and GPU accelerators are often coupled together to achieve impressive performances. However, classical B&B algorithms must be rethought to deal with their two divergent architectures. In this paper, we propose a new B&B approach exploiting both the multi-core aspect of actual processors and GPU accelerators. The proposed approaches have been executed to solve FSP instances that are well-known combinatorial optimization benchmarks. Real experiments have been carried out on an Intel Xeon 64-bit quad-core processor E5520 coupled to an Nvidia Tesla C2075 GPU device. The results show that our hybrid B&B approach speeds up the execution time up to x123 over the sequential mono-core B&B algorithm.