Scientific articles
\
Mathematics. Natural sciences
\
Mathematics
\
Operational research (OR): mathematical theories and methods
The parallel simplex-method achievements for errorless solving of linear programming problems
Section: Программирование
Article in issue: 25 (242), 2011.
Free access
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 1 is number of bits for a source data item then space complexity are no more 41m4 + o(m3), one iteration time complexity are no more O(1m4), and paralleling efficiency (i.e. ratio of acceleration to number of processors) asymptotical estimate are 100%.
linear programming
\ simplex method
\ distributed computing
\ parallel computing
\ rational computations
\ optimization
\ arbitrary precision
\ interval arithmetic
Short address: https://sciup.org/147159094
IDS: 147159094 | UDC: 519.852