On a Dual Method for a Specially Structured Linear Programming Problem with Application to Stochastic Programming

Authors: Fábián C.I.¹; Prékopa A.²; Ruf-Fiedler O.³

Source: Optimization Methods and Software, Volume 17, Number 3, 1 January 2002 , pp. 445-492(48)

Buy & download fulltext article:

Price: $56.94 plus tax (Refund Policy)

Abstract:

This article revises and improves on a Dual Type Method (DTM), developed by Prékopa. (Prékopa, A. (1990). Dual method for the solution of a one-stage stochastic programming problem with random RHS obeying a discrete probability distribution, ZOR-Methods and Models of Operations Research, 34, 441-461), in two ways. The first one allows us, in each iteration, to perform the largest step toward the optimum. The second one consists of exploiting the structure of the working basis, which has to be inverted in each iteration, and updating its inverse in product form, as it is usual in case of the standard dual method. The improved method has been implemented. A report on its performance on the solution of some stochastic programming problems is also presented.

Keywords: Linear programming; Piecewise linear functions; Stochastic programming

Document Type: Research article

Affiliations: 1: Visitor to RUTCOR, Department of OR, L. Eötvös University, P.O. Box 120, Budapest, H-1518 Hungary 2: RUTCOR, Rutgers Center for Operations Research, Rutgers University, 640 Bartholomew Road, Piscataway, NJ 08854-8003, USA 3: Swiss Reinsurance Co./Life Department Mythenquai 50/60 Zürich, CH-8022 Switzerland

Publication date: 2002-01-01