Parallel algorithms to solve two-stage stochastic linear programs with robustness constraints

In this paper we present a parallel method for solving two-stage stochastic linear programs with restricted recourse. The mathematical model considere d here can be used to represent several real-world applications, including financial and production planning problems, for which significant changes i n the recourse solutions should be avoided because of their difficulty to b e implemented. Our parallel method is based on a primal-dual path-following interior point algorithm, and exploits fruitfully the dual block-angular s tructure of the constraint matrix and the special block structure of the ma trices involved in the restricted recourse model. We describe and discuss b oth message-passing and shared-memory implementations and we present the nu merical results collected on the Origin2000. (C) 2000 Elsevier Science B.V. All rights reserved.