|
Vestnik Yuzhno-Ural'skogo Universiteta. Seriya Matematicheskoe Modelirovanie i Programmirovanie, 2011, Issue 9, Pages 107–118
(Mi vyuru179)
|
|
|
|
This article is cited in 4 scientific papers (total 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.
Received: 20.03.2011
Citation:
A. V. Panyukov, V. V. Gorbik, “The parallel simplex-method achievements for errorless solving of linear programming problems”, Vestnik YuUrGU. Ser. Mat. Model. Progr., 2011, no. 9, 107–118
Linking options:
https://www.mathnet.ru/eng/vyuru179 https://www.mathnet.ru/eng/vyuru/y2011/i9/p107
|
|