Speaker
Mr
Vladimir Voloshinov
(Institute for Information Transmission Problems RAS)
Description
Heterogeneity of optimization software (solvers and interpreters of algebraic modeling languages for optimization, e.g. AMPL, GAMS etc.) and available computing infrastructure is one of reasons complicating wide practical usage of optimization models in distributed computing mode. The problem is far from completion despite an intensive work on the subject (one of the most mature is a COIN-OR Optimization Services project [1]). In the report we present two use cases of AMPL-interpreter capabilities in distributed computing infrastructure (AMPL [2] – is one of the most popular high-level optimization modeling system). We use off-the-shelf AMPL-compatible solvers due to the expertise encapsulated in these highly tuned libraries of optimization numerical methods.
The first use case concerns running any optimization algorithm written as an AMPL-script in distributed mode, when all problems (including intermediate sub-problems) are solved by remote optimization REST-services based on off-the-shelf AMPL-compatable solvers; independent problems will be solved in parallel, thus increasing overall performance in according with the number of available solvers. The approach is based on MathCloud software toolkit [3], MathCloud Python API and AMPL-interpreter feature to interact with Bash-shell.
The second use case demonstrate solving of complex discrete optimization problems (i.e. MILP) by “coarse-grained” parallel scheme of branch-and-bound algorithm (B&B). The approach is based on preliminary analysis and decomposition of the given problem into a number of sub-problems by some special AMPL-script. Then all these subproblems are solving in parallel by a number of MILP-solvers “embedded” in a special distributed system. 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.
Uses cases, mentioned above, are demonstrated by the examples of decomposition algorithms written as AMPL-scripts and solving some discrete optimization problems (Traveling Salesmen Problem and Tasks-Workers Scheduling problem).
[1] Fourer R., Ma Jun, Martin K. Optimization Services: A Framework for Distributed Optimization // Operations Research. 2010, vol. 58, pp. 1624-1636
[2] Fourer R., Gay D.M., and Kernighan B.W. AMPL: A Modeling Language for Mathematical Programming. Thomson/Brooks/Cole, 2003, 517pp.
[3] Afanasiev A., Sukhoroslov O., Voloshinov V. MathCloud: Publication and Reuse of Scientific Applications as RESTful Web Services // Victor E. Malyshkin (Ed.): Parallel Computing Technologies (12th International Conference, PaCT 2013, St. Petersburg, Russia, September 30 — October 4, 2013). Lecture Notes in Computer Science Volume 7979. Springer 2013. pp. 394-408
Supported by the Russian Foundation for Basic Research (grant # 13-07-00987)
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)
