A Regularized Jacobi Method for Large-Scale Linear Programming

Kallio MJ, Ruszczynski A, & Salo S (1993). A Regularized Jacobi Method for Large-Scale Linear Programming. IIASA Working Paper. IIASA, Laxenburg, Austria: WP-93-061

[img]
Preview
Text
WP-93-061.pdf

Download (1MB) | Preview

Abstract

A parallel algorithm based on Jacobi iterations is proposed to minimize the augmented Lagrangian functions of the multiplier method for large-scale linear programming. Sparsity is efficiently exploited for determining stepsizes (column-wise) for the Jacobi iterations. Linear convergence is shown with convergence ratio depending on sparsity but not on the penalty parameter and on problem size. Employing simulation of parallel computations, an experimental code is tested extensively on 68 Netlib problems. Results are compared with the simplex method, an interior point algorithm and a Gauss-Seidel approach. We observe that speedup against the simplex method generally increases with the problem size, while the parallel solution times increase slowly, if at all. Our preliminary results compared with the other two methods are highly encouraging as well.

Item Type: Monograph (IIASA Working Paper)
Research Programs: Optimization under Uncertainty (OPT)
Depositing User: IIASA Import
Date Deposited: 15 Jan 2016 02:02
Last Modified: 19 Oct 2016 19:42
URI: http://pure.iiasa.ac.at/3753

Actions (login required)

View Item View Item

International Institute for Applied Systems Analysis (IIASA)
Schlossplatz 1, A-2361 Laxenburg, Austria
Phone: (+43 2236) 807 0 Fax:(+43 2236) 71 313