Implementation of Coarse-Grained Parallel Scheme of Branch-and-Bound Algorithm for Discrete Optimization in Everest Platform

5 Jul 2016, 16:00
15m
406B

406B

Sectional reports 2. Operation, monitoring, optimization in distributed computing systems 2. Operation, monitoring, optimization in distributed computing systems

Speaker

Mr Sergey Smirnov (Institute for Information Transmission Problems of the Russian Academy of Sciences)

Description

In this study we examine the coarse-grained approach to parallelization of the branch-and-bound algorithm. Our approach is that we divide a mixed-integer programming problem on a set of subproblems by fixing some of the integer variables. Subproblems are solved by open-source solvers running in parallel on multiple hosts. When solver finds an incumbent it broadcasts it and other solvers can use its objective value during solution process. Solver life cycle is managed by the Everest Web-based platform for distributed computing. The platform was also modified to allow solvers exchange messages with incumbents and other data. The system was test on several mixed-integer programming problems and a noticeable speedup was shown. The reported study was partially supported by RFBR, research project №16-07-01150 А.

Primary author

Mr Sergey Smirnov (Institute for Information Transmission Problems of the Russian Academy of Sciences)

Co-authors

Dr Oleg Sukhoroslov (IITP RAS) Mr Vladimir Voloshinov (Institute for Information Transmission Problems RAS)

Presentation materials

There are no materials yet.