Shared-memory implementation of the path-following algorithm to solve stochastic linear programs with robustness constraints
by
Chefi Triki
University of Calabria
Coauthors: Patrizia Beraldi, Roberto Musmanno

Stochastic programming has shown to be an effective tool to solve several real-world problems in which data are characterized by uncertainty and incompleteness [3]. Finance is one of the most challenging fields which is highly affected by uncertainty and that could take, as consequence, full advantage of the stochastic framework. Uncertainty can be incorporated into the mathematical model in terms of discrete random variables by a set of scenarios. The number of scenarios is typically very large and this leads to huge deterministic equivalent problems which are very difficult to solve by using conventional computing systems.

The new advances in high performance computing gives an opportunity to overcome these computational limits and offers the possibility to solve large scale stochastic problems efficiently [6].

We propose a shared-memory implementation of a primal-dual path-following algorithm to solve general two-stage model. Robustness conditions are also introduced with the aim to restrict the dispersion among recourse decisions. The restricted recourse approach, proposed originally by Vladimirou and Zenios in [4], is required in many real applications in which substantially different second-stage decisions are difficult to implement.

The computation of the dual step, which is the most expensive part of the proposed method, is performed by using the Birge-Qi factorization as described in [2, 5] to exploit the dual block-angular structure of the matrix constraints. A specialized decomposition procedure that takes further advantages from the matrices involved in the restricted recourse model was proposed and implemented on serial settings in [1].

We present and discuss experimental results, carried out on the Origin 2000 supercomputer, using a set of standard test problems with increasing number of scenarios.

[1] P. Beraldi, R. Musmanno, and C. Triki. Solving stochastic linear programs with restricted recourse using interior point methods. Technical Report 03-97, Dipartimento di Elettronica, Informatica e Sistemistica, Università della Calabria, 87036 Rende, Italy, 1997. (Accepted for publication on Comptational Optimization and Applications).

[2] J. R. Birge and D. F. Holmes. Efficient solution of two-stage stochastic linear programs using interior point methods. Computational Optimization and Applications, 1:245-276, 1992.

[3] J. R. Birge and F. V. Louveaux. Introduction to Stochastic Programming. Springer-Verlag, 1997.

[4] H. Vladimirou and S. A. Zenios. Stochastic linear programs with restricted recourse. European J. of Operations Research, 101:177-192, 1997.

[5] D. Yang and S. A. Zenios. A scalable parallel interior point algorithm for stochastic linear programming and robust optimization. Computational Optimization and Applications, 7:143-158, 1997.

[6] S. Zenios and Y. Censor. Parallel Optimization: Theory, Algorithms and Applications. Oxford University Press, 1997.

Date received: February 16, 1999

Copyright © 1999 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cacq-11.