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's take some discrete optimization problem and a time interval to find its solution by some branch and bound solver. Can we reduce time of solving if a number of instances of the same solver will run simultaneously with the same problem? We have got significant acceleration with open source solvers in multi-processors cloud computing environment. Our approach is based on the following:

• preliminary decomposition of the given problem into sub-problems via fixing integer values of some discrete variables selected in accordance with some heuristic rule implemented as a program in optimization modelling language AMPL;
• parallel solving of sub-problems by a pool of solvers which run simultaneously and exchange incumbents (bounds of optimal values in branch-and-bound method) they found in processing of sub-problems.

The approach is attractive due to the relative simplicity of program implementation. It has been verified on “Traveling Salesman (TSP)” and “Task-to-Worker scheduling” problems. (In Russian).