Speaker
Mr
Vladimir Voloshinov
(Institute for Information Transmission Problems RAS)
Description
The report presents an new approach to solving rather hard discrete and global optimization problems in Everest, http://everest.distcomp.org, a web-based distributed computing platform.
The platform enables convenient access to heterogeneous resources (standalone servers, high performance clusters etc.) by means of domain-specific computational web services, development and execution of many-task applications, and pooling of multiple resources for running distributed computations.
Rather generic Everst-application had been implemented for solving discrete and global optimization problems - so called DDBNB, Domain Decomposition Branch-and-Bound, https://github.com/distcomp/ddbnb. DDBNB implements a kind of coarse-grained parallelization of Branch-and-Bound (BNB) method. It supports two strategies (including combined usage of both): decomposition of feasible domain into a set of sub-problems; multisearch (or concurrent) solving the same problem with different settings of the BNB-method. In both cases several BNB-solver's processes exchange incumbents, best values of goal function on feasible solutions, they found. DDBNB uses generic Everest messaging service and open source solvers : CBC, https://projects.coin-or.org/Cbc; SCIP, http://scip.zib.de.
By now we got some experience in solving different optimization problems: Travelling Salesman Problem (TSP) as Mixed-Integer Linear Programming; global optimization problems with all continuous variables (so called Tammes and Thomson problems, both relate to sphere packing) and global optimization with continuous and binary variable (so called Flat Torus Packing problems). For TSP, computing experiments are presented, when DDBNB worked in different modes: Domain Decomposition only, multisearch only; combined mode.
As to global optimization, all problems had been reduced to the form of mathematical programming problems with polynomial functions (solver SCIP supports solving of such class of problems). Here, only Domain Decomposition had been used and different methods of decomposition in the case of sphere's and torus's packing and corresponding computing experiments are presented.
Formulation of original problems and decomposition strategies have been implemented via Pyomo, http://www.pyomo.org. All sub-problems have been passed to solvers as AMPL-stubs, (also known as NL-files). Usage of Everest platform enables to involve in experiments computing resources of Center for Distributed Computing, http://distcomp.ru, HPCs of NRC Kurchatov Institute and South Ural State University.
The reported study was funded by RFBR according to the research projects #18-07-01175 and #18-07-00956.
Primary author
Mr
Vladimir Voloshinov
(Institute for Information Transmission Problems RAS)
Co-author
Mr
Sergey Smirnov
(Institute for Information Transmission Problems of the Russian Academy of Sciences)
