Parallel implementation of Newton's method for solving large-scale linear programs

被引：12

作者：

Garanzha, V. A. ^{[1
]}

Golikov, A. I. ^{[1
]}

Evtushenko, Yu. G. ^{[1
]}

Nguen, M. Kh. ^{[1
]}

机构：

[1] Russian Acad Sci, Ctr Comp, Moscow 119333, Russia

来源：

COMPUTATIONAL MATHEMATICS AND MATHEMATICAL PHYSICS | 2009年 / 49卷 / 08期

基金：

俄罗斯基础研究基金会;

关键词：

linear programming; generalized Newton's method; unconstrained optimization; parallel computations;

D O I：

10.1134/S096554250908003X

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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.

引用

页码：1303 / 1317

页数：15

共 15 条

[1]

Andersen E.D., 2000, High Performance Optimization, P197, DOI [DOI 10.1007/978-1-4757-3216-08, DOI 10.1007/978-1-4757-3216-0_8]

[2]

[Anonymous], COMP MATH MATH PHYS

[3]

Brodal GS, 2004, LECT NOTES COMPUT SC, V3111, P3

[4]

COLEMAN TF, 1997, P 8 SIAM C PAR PROC

[5]

EREMIN II, 1998, LINEAR OPTIMIZATION

[6]

Frigo Matteo., 1999, PROC 40 ANN S FDN CO, P285

[7]

Golikov A.I., 2004, Comput. Math. Math. Phys, V44, P1484

[8]

Golikov AI, 2004, DOKL MATH, V70, P615

[9] On the minimum norm solution of linear programs [J].

Kanzow, C ;

Qi, H ;

Qi, L .

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, 2003, 116 (02) :333-345

[10]

Kaporin IE, 1998, NUMER LINEAR ALGEBR, V5, P483, DOI 10.1002/(SICI)1099-1506(199811/12)5:6<483::AID-NLA156>3.3.CO

← 1 2 →