Implementation and Use of Coarse-grained Parallel Branch-and-bound in Everest Distributed Environment

This paper examines the coarse-grained approach to parallelization of the branch-and-bound (B&B) algorithm in a distributed computing environment. This approach is based on preliminary decomposition of a feasible domain of mixed-integer programming problem into a set of subproblems. The produced subproblems are solved in parallel by a distributed pool of standalone B&B solvers. The incumbent values found by individual solvers are intercepted and propagated to other solvers to speed up the traversal of B&B search tree. Presented implementation of the approach is based on SCIP, a non-commercial MINLP solver, and Everest, a web-based distributed computing platform. The implementation was tested on several mixed integer programming problems and a noticeable speedup has been achieved. In the paper, results of a number of experiments with the Traveling Salesman Problem are presented. (C) 2017 The Authors. Published by Elsevier B.V. Peer-review under responsibility of the scientific committee of the International Conference on Computational Science