Speaker
Mr
Vladimir Voloshinov
(Institute for Information Transmission Problems RAS)
Description
Optimization models are widely applied in the most different research areas (natural sciences, technology, economy, sociology etc.). But, heterogeneity of available optimization software and computing infrastructure complicates widespread practical usage of this approach. Especially, it is so for small and venture research teams at the beginning phase of work during optimization model fitting (including input and output data), selection of relevant algorithm and solvers, evaluating of required computing power and available computing resources (standalone servers, clusters, clouds and/or Grid infrastructure).
To now, there are exist a large reserve in the theory and numerical methods for solving optimization problems of different types. We have a wide choice of optimization software: 1) solvers for mathematical programming, discrete optimization, optimal control problems etc.; 2) a number of translators for optimization modeling algebraic languages (AMPL, GAMS, ZIMPL, Fico-XPRESS etc.) compatible with most of solvers.; 3) another special scientific software, e.g. Computer Algebra Systems (Stochastic, Geometry etc, as well). Dynamic systems optimization (e.g. optimal control) involve solution of Cauchy and/or boundary-value problems. Despite the fact that some of solvers may run in multi-threaded or parallel (on clusters) modes, complexity of the considering problems increases and it requires the use of more powerful computing systems.
Although active development of technologies for running optimization software as Web- or REST-services the work is far from completion. Still we don't have conventional, generally accepted technology for "on-demand" deployment of high-performance problem-oriented optimization modeling systems on the base of solvers and optimization languages translators running in distributed heterogeneous computing infrastructure (including standalone servers, clusters, clouds and Grid).
At the beginning of the report we present survey of existing technologies of optimization modeling in distributed computing environment: from “NEOS: server for optimization”,
http://www.neos-server.org (Argonne National Laboratory, University of Wisconsin) and framework «OS:
Optimization Services», http://www.optimizationservices.org to one of the most recent Fico Optimization Suite running at Fico Analytic Cloud, http://www.fico.com/en/analytics/optimization.
Then we present our approach based on Everest, http://everest.distcomp.org, a cloud platform for researchers supporting publication, execution and composition of applications running across distributed heterogeneous computing infrastructure. Everest software is developing by our research team in Center for Distributed Computing, http://distcomp.ru.
We demonstrate a number of optimization models implemented by Everest platform. All of them are based on REST-services providing remote access to LP/MILP/NLP solvers and to AMPL-translator. We provide an extension of AMPL (so called AMPLX, https://gitlab.com/ssmir/amplx) which allows running any AMPL-script (data processing algorithm involving optimization written in AMPL language) in distributed mode, when independent problems are solved in parallel by remote solvers. As example an implementation of a branch-and-bound algorithm of carbonaceous nanomaterial structure identification with a joint X-Ray and neutron diffraction data analysis.
Another example concerns implementation of coarse grained type of branch-and-bound algorithm with preliminary static decomposition of initial MILP problems into a fixed number of sub-problems in accordance with some heuristic rules implemented as an AMPL-script. Then all these subproblems are solving in parallel by a number of MILP-solvers connected to Everest. This system provides exchange of B&B “incumbents” (the best known feasible solution found in the branching tree) between solvers. This exchange accelerates the search of optimal solution of the initial MILP-problem. This approach is demonstrated via Traveling Salesmen Problem and Tasks-Workers Scheduling problems.
Primary author
Prof.
Alexander Afanasiev
(IITP RAS)
Co-author
Mr
Vladimir Voloshinov
(Institute for Information Transmission Problems RAS)
