Many practical problems in industrial and social planning require optimal decisions to be made periodically through time. Linear programs, called dynamic linear programs, can often be formulated to model the requirements of these decision processes. These programs are generally quite large and difficult to solve. The search for efficient methods in finding their optimal solutions has been a major topic in operations research for the past 25 years.
Often the problem modeled by a dynamic linear program involves uncertainties which can complicate and exponentially increase the program's size. There may be several possible outcomes in the future, but deterministic linear programs usually consider only the most likely outcome. In this dissertation, we present methods for solving the stochastic dynamic linear program, the dynamic linear program with uncertainties explicitly included.
Our methods take advantage of the program structure. Dynamic linear programs are characterized by a staircase structured coefficient matrix, in which non-zero elements appear only in blocks along the diagonal or adjacent to the diagonal. This structure makes many efficient techniques possible. We show that the stochastic model's specific structure also leads to procedures that may reduce the computational cost of solutions for these problems.
Our development of these solution techniques begins with a presentation of conditions under which the stochastic problem need not be solved, that is, where the solution of a deterministic problem is the optimal solution of the stochastic problem. These conditions are often not satisfied, however, and a deterministic solution can frequently lead to significant losses relative to a stochastic solution. This possibility motivates our finding solutions to the stochastic program.
The methods we present for solving these programs are based upon three major large-scale optimization techniques: decomposition, partitioning, and basis factorization. The first two methods are basically dynamic programming approaches in which the state space is locally approximated. The structure of the program then allows for additional efficiency to be gained in following our procedures toward optimality. The third method exploits the repeated block structure of the entire program in reducing the storage and computational requirements of the revised simplex method.
Computational experience with these methods was restricted to a variety of small problems taken from examples in optimal control, production and energy. The results on these small examples showed that some computational advantage may result from our techniques. The true test of these methods, however, will be in their application to larger problems that model practical situations.
My Research