Publication

De Silva, A. and Abramson, D. A. 1996 , "Parallel algorithms for solving Stochastic Linear Programs", Chapter 38, pp 1097 -1115, Handbook of Parallel and Distributed Computing, McGraw Hill, Ed Albert Zomaya, ISBN 0-073020-2,

Abstract

Parallel and distributed computing platforms are beginning to revolutionise the traditional engineering design process. Rather than performing direct experiments, researchers are now able to simulated extremely complex systems based on numerical models. When appropriately formulated, these models allow the designer to predict the behaviour of real systems with great accuracy. However, the cost of such accuracy is a requirement for very large amounts of computing time. Until the advent of cheaply available parallel systems, very expensive super computers were required in order to use numerical simulation in this way. Because of the numeric techniques which are employed to solve the systems of equations in the models, it is often possible to achieve very high levels of performance from parallel systems.

Operations research techniques have been used for many years to allow engineers to optimise some aspect of their design. As in the simulation process discussed above, mathematical models are constructed which describe the problem, and then various algorithms can be applied to solve the system. However, up to date, there has been very limited application of parallel computers to these problems. The main reason for this is that many operations research algorithms are highly sequential, and thus, it is not easy to achieve good speedups on large parallel systems.

The problem with many operations research models is that the designer must make simplifications in the original real world problem in order to produce a system which can be solved in a reasonable time. One area where this is particularly relevant is in the process of incorporating uncertainty into the system. Traditionally, models are specified with exact values for parameters, and the sensitivity to those parameters is rarely explored. Stochastic programming is a technique which allows uncertainty to be incorporated in a problem's specification, and thus it is possible to produce a solution which takes account of the variance which is experienced in the real world. However, using conventional sequential computers, it is not possible to solve very large problems, because the model size becomes very large. Fortunately, some stochastic systems contain highly parallel data structures, and these can be exploited by parallel computers. Recently there has been quite a degree of research activity in this area.

This chapter examines methods used for solving large linear stochastic optimisation problems using parallel computers. Because this is a relatively new field of operations research there are very few survey articles on the topic. Section 1 introduces the use of linear programming, and stochastic optimisation. The methods are illustrated through a very simple example. The advanced reader may choose to skip section 2. In section 2 we present an overview of the various techniques which can be used to solve linear stochastic programs, and we look at their implementation on parallel systems. In section 3, we present a comparison of the performance of the various methods.

Download

chapter.pdf