Decomposition algorithm for linear programming problems without a block structure in the Everest computing environment

Abstract

The article describes decomposition method for solving linear programming problems in a general case when it is impossible or difficult to reveal the block structure (of the constraint matrix) used by the classic Danzig-Wulf or Benders decomposition algorithms. Instead, an arbitrary partition of the constraint matrix into a number of submatrices corresponding to groups of rows is used. As in the Danzig-Wolfe algorithm, one searches a maximum of a concave function (on dual variables) by a subgradient method. Iterative routine of solving the original problem includes the phases of solving sets of independent subproblems of a smaller dimension than the original one. Number of submatrices (and subproblems) depends on the dimension of the original problem and the computational power of the distributed environment, where parallel solving of above independent subproblems is done. In concrete term, it is proposed to use the optimization services deployed on the Everest platform, everest.distcomp.org. Programming of the algorithm and data exchange with solvers connected to Everest, may be done by AMPLX system based on algebraic optimization modeling language AMPL, ampl.com. Also, instead of the commercial translator AMPL, it is possible to use the Python interpreter and the freely available Pyomo package, pyomo.org, which provides interaction with AMPL-compatible solvers. The software implementation of the algorithm by Everest platform, allows to hope to get a noticeable acceleration when solving large-scale problems.