A branch-and-bound algorithm using multiple GPU-based LP solvers

Meyer, Xavier (Department of Computer Science, University of Geneva, Geneva, Switzerland) ; Chopard, Bastien (Department of Computer Science, University of Geneva, Geneva, Switzerland) ; Albuquerque, Paul (School of Engineering, Architecture and Landscape (hepia), HES-SO // University of Applied Sciences Western Switzerland)

The Branch-and-Bound (B&B) method is a well-known optimization algorithm for solving integer linear programming (ILP) models in the field of operations research. It is part of software often employed by businesses for finding solutions to problems such as airline scheduling problems. It operates according to a divide-and-conquer principle by building a tree-like structure with nodes that represent linear programming (LP) problems. A LP solver commonly used to process the nodes is the simplex method. Nowadays its sequential implementation can be found in almost all commercial ILP solvers. In this paper, we present a hybrid CPU-GPU implementation of the B&B algorithm. The B&B tree is managed by the CPU, while the revised simplex method is mainly a GPU implementation, relying on the CUDA technology of NVIDIA. The CPU manages concurrently multiple instances of the LP solver. The principal difference with a sequential implementation of the B&B algorithm pertains to the LP solver, provided that the B&B tree is managed with the same strategy. We thus compared our GPU-based implementation of the revised simplex to a well-known open-source sequential solver, named CLP, of the COIN-OR project. For given problem densities, we measured a size threshhold beyond which our GPU implementation outperformed its sequential counterpart.

Conference Type:
full paper
Ingénierie et Architecture
HEPIA - Genève
inIT - Institut d'Ingénierie Informatique et des Télécommunications
Bangalore, India, 18-21 December 2013
Bangalore, India
18-21 December 2013
10 p.
Published in:
Proceedings of 20th Annual International Conference on High Performance Computing, 18-21 December 2013, Bangalore, India
Numeration (vol. no.):
pp. 129-138
Appears in Collection:

Note: The status of this file is: restricted

 Record created 2020-07-10, last modified 2020-10-27

Download fulltext

Rate this document:

Rate this document:
(Not yet reviewed)