• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

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

Procedia Computer Science. 2017. Vol. 108. P. 1532-1541.
Voloshinov V., Smirnov S., Sukhoroslov O. V.

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.