Geodesic
The parallel simplex-method achievements for errorless solving of linear programming problems
Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie, no. 9 (2011), pp. 107-118 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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. 
@article{VYURU_2011_9_a10,
     author = {A. V. Panyukov and V. V. Gorbik},
     title = {The parallel simplex-method achievements for errorless solving of linear programming problems},
     journal = {Vestnik \^U\v{z}no-Uralʹskogo gosudarstvennogo universiteta. Seri\^a, Matemati\v{c}eskoe modelirovanie i programmirovanie},
     pages = {107--118},
     year = {2011},
     number = {9},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VYURU_2011_9_a10/}
}
TY  - JOUR
AU  - A. V. Panyukov
AU  - V. V. Gorbik
TI  - The parallel simplex-method achievements for errorless solving of linear programming problems
JO  - Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie
PY  - 2011
SP  - 107
EP  - 118
IS  - 9
UR  - http://geodesic.mathdoc.fr/item/VYURU_2011_9_a10/
LA  - ru
ID  - VYURU_2011_9_a10
ER  - 
%0 Journal Article
%A A. V. Panyukov
%A V. V. Gorbik
%T The parallel simplex-method achievements for errorless solving of linear programming problems
%J Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie
%D 2011
%P 107-118
%N 9
%U http://geodesic.mathdoc.fr/item/VYURU_2011_9_a10/
%G ru
%F VYURU_2011_9_a10
A. V. Panyukov; V. V. Gorbik. The parallel simplex-method achievements for errorless solving of linear programming problems. Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie, no. 9 (2011), pp. 107-118. http://geodesic.mathdoc.fr/item/VYURU_2011_9_a10/

[1] V. A. Garanzha, A. I. Golikov, Yu. G. Evtushenko, “Parallelnaya realizatsiya metoda Nyutona dlya resheniya bolshikh zadach lineinogo programmirovaniya”, Zhurn. vychisl. mat. i mat. fiziki, 49:8 (2009), 1369–1384 | MR | Zbl

[2] Ju. Hall, “Towards a practical parallelization of the simplex method”, J. Computational Management Science, 7:2 (2010), 139–170 | DOI | MR | Zbl

[3] A. V. Panyukov, V. V. Gorbik, “Exact and Guaranteed Accuracy Solutions of Linear Programming Problems by Distributed Computer Systems with MPI”, Tambov University REPORTS: A Theoretical and Applied Scientific Journal. Series: Natural and Technical Sciences, 15:4 (2010), 1392–1404 http://vestnik.tsutmb.ru/old/index.php?module=subjects&func=viewpage&pageid=165

[4] A. V. Panyukov, M. I. Germanenko, V. V. Gorbik, “Biblioteka klassov «Exact Computational»”, Programmy dlya EVM, bazy dannykh, topologii integralnykh mikroskhem: ofitsialnyi byulleten Ros. agentstva po patentam i tovarnym znakam, 2009, no. 3, 251

[5] A. V. Panyukov, M. I. Germanenko, V. V. Gorbik, “Parallelnye algoritmy resheniya sistem lineinykh algebraicheskikh uravnenii s primeneniem vychislenii bez okrugleniya”, Parallelnye vychislitelnye tekhnologii, PAVT-2007, Tr. mezhdunar. nauch. konf. (Chelyabinsk, 29 yanvarya–2 fevralya 2007 g.), v. 2, Izd-vo YuUrGU, Chelyabinsk, 2007, 238–249

[6] A. V. Panyukov, M. I. Germanenko, “Prilozhenie dlya bezoshibochnogo nakhozhdeniya obobschennoi obratnoi matritsy metodom Mura–Penrouza i bezoshibochnoe reshenie sistem lineinykh algebraicheskikh uravnenii”, Informatsionnye tekhnologii modelirovaniya i upravleniya, 2009, no. 1(53), 78–87

[7] F. P. Vasilev, A. Yu. Ivanitskii, Lineinoe programmirovanie, Izd-vo Faktorial Press, M., 2003, 352 pp. | MR