Effective use of discrete optimization solvers in cloud infrastructure on the basis of heuristic decomposition of the initial problem by optimization modeling system AMPL

Let the process of finding a solution in some problem of discrete optimization by a package implementing the algorithm of branches and boundaries take a certain time. Is it possible to speed up the solution of the same problem if we have a computing environment where we can run several simultaneously running "instances" of the same optimization package? The report discusses a way to get a noticeable acceleration for open source packages in a virtual multiprocessor computing environment. The approach is based on the following: (1) preliminary decomposition of the original problem into several sub-tasks by fixing the integer (boolean) values ​​of a part of the discrete variables selected according to some heuristic rule implemented in the form of a program in the high-level language of AMPL optimization modeling; (2) simultaneous solution of the subtasks obtained by the copies of the same package, with the added possibility of exchanging the found record values ​​of the objective function. The proposed approach attracts relative simplicity of the software implementation and is demonstrated by examples of solving the traveling salesman problem and scheduling the assignment of work to the executors