Scalable algorithm for non-stationary linear programming problems solving
Irina M. Sokolinskaya · 2017
The paper describes a new scalable algorithm called NSLP for high-dimension, non-stationary linear programming problem solving on the modern cluster computing systems. The algorithm consists of two phases: Quest and Targeting. The Quest phase calculates a solution for the system of inequalities defining the constraint system of the linear programming problem under the condition of the input data dynamic changes. To do this, it uses the apparatus of Fejer maps. The Targeting phase forms a special system of points having the shape of the n-dimensional axisymmetric cross. The cross moves in the n-dimensional space in such a way that the solution of the linear programming problem is permanently in the ε-vicinity of the cross central point.