Geodesic
Parallel implementation of Newton's method for solving large-scale linear programs
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 49 (2009) no. 8, pp. 1369-1384 
V. A. Garanzha; A. I. Golikov; Yu. G. Evtushenko; M. Kh. Nguen. Parallel implementation of Newton's method for solving large-scale linear programs. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 49 (2009) no. 8, pp. 1369-1384. http://geodesic.mathdoc.fr/item/ZVMMF_2009_49_8_a2/
@article{ZVMMF_2009_49_8_a2,
     author = {V. A. Garanzha and A. I. Golikov and Yu. G. Evtushenko and M. Kh. Nguen},
     title = {Parallel implementation of {Newton's} method for solving large-scale linear programs},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {1369--1384},
     year = {2009},
     volume = {49},
     number = {8},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2009_49_8_a2/}
}
TY  - JOUR
AU  - V. A. Garanzha
AU  - A. I. Golikov
AU  - Yu. G. Evtushenko
AU  - M. Kh. Nguen
TI  - Parallel implementation of Newton's method for solving large-scale linear programs
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2009
SP  - 1369
EP  - 1384
VL  - 49
IS  - 8
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2009_49_8_a2/
LA  - ru
ID  - ZVMMF_2009_49_8_a2
ER  - 
%0 Journal Article
%A V. A. Garanzha
%A A. I. Golikov
%A Yu. G. Evtushenko
%A M. Kh. Nguen
%T Parallel implementation of Newton's method for solving large-scale linear programs
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2009
%P 1369-1384
%V 49
%N 8
%U http://geodesic.mathdoc.fr/item/ZVMMF_2009_49_8_a2/
%G ru
%F ZVMMF_2009_49_8_a2

Voir la notice de l'article provenant de la source Math-Net.Ru

Parallel versions of a method based on reducing a linear program (LP) to an unconstrained maximization of a concave differentiable piecewise quadratic function are proposed. The maximization problem is solved using the generalized Newton method. The parallel method is implemented in C using the MPI library for interprocessor data exchange. Computations were performed on the parallel cluster MVC-6000IM. Large-scale LPs with several millions of variables and several hundreds of thousands of constraints were solved. Results of uniprocessor and multiprocessor computations are presented.

[1] Eremin I. I., Teoriya lineinoi optimizatsii, Izd-vo UrO RAN, Ekaterinburg, 1998

[2] Vasilev F. P., Ivanitskii A. Yu., Lineinoe programmirovanie, Faktorial, M., 2003 | MR

[3] Golikov A. I., Evtushenko Yu. G., “Metod resheniya zadach lineinogo programmirovaniya bolshoi razmernosti”, Dokl. RAN, 397:6 (2004), 727–732 | MR

[4] Golikov A. I., Evtushenko Yu. G., Mollaverdi N., “Primenenie metoda Nyutona k resheniyu zadach lineinogo programmirovaniya bolshoi razmernosti”, Zh. vychisl. matem. i matem. fiz., 44:9 (2004), 1564–1573 | MR | Zbl

[5] Golikov A. I., Evtushenko Yu. G., “Otyskanie normalnykh reshenii v zadachakh lineinogo programmirovaniya”, Zh. vychisl. matem. i matem. fiz., 40:12 (2000), 1766–1786 | MR | Zbl

[6] Ranzow C., Qi H., Qi L., “On the Minimum Norm Solution of Linear Programs”, J. Optimizat. Theory and Appl., 116 (2003), 333–345 | DOI | MR

[7] Mangasarian O. L., “A Newton Method for Linear Programming”, J. Optimizat. Theory and Appl., 121 (2004), 1–18 | DOI | MR | Zbl

[8] Meszaros Cs., “The BPMPD interior point solver for convex quadratic programming problems”, Optimizat. Meth. and Software, 11–12 (1999), 431–449 | DOI | MR | Zbl

[9] Andersen E. D., Andersen K. D., “The MOSEK interior point optimizer for linear programming: an implementation of homogeneous algorithm”, High Performance Optimizat., Kluwer, New York, 2000, 197–232 | MR | Zbl

[10] Karypis G., Gupta A., Kumar V., “A parallel formulation of interior point algorithms”, Proc. Supercomputing, 1994, 204–213

[11] Coleman T. F., Czyzyk J., Sun C., Wagner M., Wright S. J., “pPCx: Parallel software for linear programming”, Proc. Eighth SIAM Conf. Parallel Proc. Sci. Comput. PPSC 1997 (March 14–17, 1997), SIAM, Minneapolis, Minnesota, USA, 1997 | MR

[12] Kaporin I. E., “High quality preconditioning of a general symmetric positive definite matrix based on its $U^{\mathsf T}U+U^{\mathsf T}R+R^{\mathsf T}U$-decomposition”, Numer. Linear Algebra Appl., 5 (1998), 483–509 | 3.0.CO;2-7 class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[13] Frigo M., Leiserson C. E., Prokop H., Ramachandran S., “Cache-oblivious algorithms”, Proc. 40th Ann. Symposium on Foundations of Computer Sci., New York, October, 1999, 285–297

[14] Brodal G. S., “Cache-oblivious algorithms and data structures”, Proc. 9th Scandinavian Workshop on Algorithm Theory, Lect. Not. in Comput. Sci., 3111, Springer, Berlin, 2004, 3–13 | MR | Zbl