On an iterative method for solving linear programming problems on cluster computing systems

L. B. Sokolinskii, I. M. Sokolinskaya

South Ural State University, Chelyabinsk

Abstract: The paper is devoted to a new method for solving large-scale linear programming (LP) problems. This method is called the apex-method. The apex-method uses the predictor-corrector framework. Thepredictor step calculates a point belonging to the feasible region of the LP problem. The corrector step calculates a sequence of points converging to the exact solution of the LP problem. The paper gives a formal description of the apex-method and provides information about its parallel implementation in C++ language using the MPI library. The results of large-scale computational experiments on a cluster computing system to study the scalability of the apex method are discussed.

Keywords: linear programming; large-scale problems; apex-method; predictor-corrector framework; iterative method; parallel algorithm; cluster computing system.

UDC: 519.688

Received: 28.06.2020

DOI: 10.26089/NumMet.v21r328

Bibliographic databases:

•