Monte Carlo application and gradient appliance for solving large scale linear programming problems: Essence and laboriousness

Abstract

We propose two recently developed iterative algorithms for solving large scale linear programming problems: the first one is based on the gravitation centers method, which in its turn widely uses Monte Carlo statistical test method, and the second one is realized on the basis of the constant step gradient method. Though the developed iterative algorithms are approximate, it is rather worthwhile in most cases to apply them when solving large scale linear problems, as they are characterized by positive properties, such as simplicity of the algoritm and the program, high-speed performance, and besides the appropriate software is free of such an unpleasant, specific for the simplex method event as a “loop”. We present some computational results. We assess the both developed algorithms with respect to a high-speed performance criterion and compare their high-speed performance with the one of the simplex method.