RUS  ENG
Full version
JOURNALS // Vestnik Yuzhno-Ural'skogo Universiteta. Seriya Matematicheskoe Modelirovanie i Programmirovanie // Archive

Vestnik YuUrGU. Ser. Mat. Model. Progr., 2011 Issue 9, Pages 107–118 (Mi vyuru179)

This article is cited in 4 papers

Programming

The parallel simplex-method achievements for errorless solving of linear programming problems

A. V. Panyukov, V. V. Gorbik

South Ural State University, Chelyabinsk

Abstract: Techniques of obtaining exact solutions of linear programming problems are subjects of this paper. Absolute accuracy are arrived at implementation of simplex-algorithm with exact rational-fractional computation. In this case if $m$ is minimal of problem dimensions, and $l$ is number of bits for a source data item then space complexity are no more $4lm^4+o(m^3)$, one iteration time complexity are no more $O(lm^4)$, and paralleling efficiency (i.e. ratio of acceleration to number of processors) asymptotical estimate are 100%.

Keywords: linear programming, simplex method, distributed computing, parallel computing, rational computations, optimization, arbitrary precision, interval arithmetic.

UDC: 519.852

Received: 20.03.2011



© Steklov Math. Inst. of RAS, 2024