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)
