Computing Block-Angular Karmarkar Projections with Applications to Stochastic Programming

We present a variant of Karmarkar's algorithm for block-angular structured linear programs, such as stochastic linear programs. By computing the projection efficiently, we give a worst-case bound on the order of the running time that can be an order of magnitude better than that of Karmarkar's standard algorithm. Further implications for approximations and very large-scale problems are given.

MoreLess

Year of publication:	1988
Authors:	Birge, John R. ; Qi, Liqun
Published in:	Management Science. - Institute for Operations Research and the Management Sciences - INFORMS, ISSN 0025-1909. - Vol. 34.1988, 12, p. 1472-1479
Publisher:	Institute for Operations Research and the Management Sciences - INFORMS
Subject:	linear programming \| stochastic programming \| Karmarkar method

More details

Extent:	application/pdf
Type of publication:	Article
Other identifiers:	10.1287/mnsc.34.12.1472 [DOI]
Source:	RePEc - Research Papers in Economics

Persistent link: https://www.econbiz.de/10009208794