Evaluation of a coarse-grained branch-and-bound algorithm in the Everest computing environment

The study concerned the coarse-grained approach to the implementation of the parallel branch-and-bound (B&B) method. Feasible domain of the mixed integer programming problem is divided into several subsets by fixing some of the integer variables. It corresponds to decomposition of the initial problem into subproblems, which are being solved in parallel by a pool of solvers. When solver finds an incumbent value it is broadcasted to other solvers. Such exchange of optimal objective value's bounds allows to speed up the solution of subproblems via reducing number of nodes of B&B search tree, which are to be explored. Solver life cycle and incumbent values' exchange are managed by the Everest Web-based platform for distributed computing, everest.distcomp.org. The system has been tested on several randomly generated mixed-integer programming problems and a noticeable speedup has been detected. (in Russian)