Two-stage stochastic linear programming: Stochastic decomposition approaches.

Persistent Link:
http://hdl.handle.net/10150/185342
Title:
Two-stage stochastic linear programming: Stochastic decomposition approaches.
Author:
Yakowitz, Diana Schadl.
Issue Date:
1991
Publisher:
The University of Arizona.
Rights:
Copyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.
Abstract:
Stochastic linear programming problems are linear programming problems for which one or more data elements are described by random variables. Two-stage stochastic linear programming problems are problems in which a first stage decision is made before the random variables are observed. A second stage, or recourse decision, which varies with these observations compensates for any deficiencies which result from the earlier decision. Many applications areas including water resources, industrial management, economics and finance lead to two-stage stochastic linear programs with recourse. In this dissertation, two algorithms for solving stochastic linear programming problems with recourse are developed and tested. The first is referred to as Quadratic Stochastic Decomposition (QSD). This algorithm is an enhanced version of the Stochastic Decomposition (SD) algorithm of Higle and Sen (1988). The enhancements were designed to increase the computational efficiency of the SD algorithm by introducing a quadratic proximal term in the master program objective function and altering the manner in which the recourse function approximations are updated. We show that every accumulation point of an easily identifiable subsequence of points generated by the algorithm are optimal solutions to the stochastic program with probability 1. The various combinations of the enhancements are empirically investigated in a computational experiment using operations research problems from the literature. The second algorithm is an SD based algorithm for solving a stochastic linear program in which the recourse problem appears in the constraint set. This algorithm involves the use of an exact penalty function in the master program. We find that under certain conditions every accumulation point of a sequence of points generated by the algorithm is an optimal solution to the recourse constrained stochastic program, with probability 1. This algorithm is tested on several operations research problems.
Type:
text; Dissertation-Reproduction (electronic)
Keywords:
Dissertations, Academic; Operations research; Stochastic programming.
Degree Name:
Ph.D.
Degree Level:
doctoral
Degree Program:
Systems and Industrial Engineering; Graduate College
Degree Grantor:
University of Arizona
Advisor:
Higle, Julia L.

Full metadata record

DC FieldValue Language
dc.language.isoenen_US
dc.titleTwo-stage stochastic linear programming: Stochastic decomposition approaches.en_US
dc.creatorYakowitz, Diana Schadl.en_US
dc.contributor.authorYakowitz, Diana Schadl.en_US
dc.date.issued1991en_US
dc.publisherThe University of Arizona.en_US
dc.rightsCopyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.en_US
dc.description.abstractStochastic linear programming problems are linear programming problems for which one or more data elements are described by random variables. Two-stage stochastic linear programming problems are problems in which a first stage decision is made before the random variables are observed. A second stage, or recourse decision, which varies with these observations compensates for any deficiencies which result from the earlier decision. Many applications areas including water resources, industrial management, economics and finance lead to two-stage stochastic linear programs with recourse. In this dissertation, two algorithms for solving stochastic linear programming problems with recourse are developed and tested. The first is referred to as Quadratic Stochastic Decomposition (QSD). This algorithm is an enhanced version of the Stochastic Decomposition (SD) algorithm of Higle and Sen (1988). The enhancements were designed to increase the computational efficiency of the SD algorithm by introducing a quadratic proximal term in the master program objective function and altering the manner in which the recourse function approximations are updated. We show that every accumulation point of an easily identifiable subsequence of points generated by the algorithm are optimal solutions to the stochastic program with probability 1. The various combinations of the enhancements are empirically investigated in a computational experiment using operations research problems from the literature. The second algorithm is an SD based algorithm for solving a stochastic linear program in which the recourse problem appears in the constraint set. This algorithm involves the use of an exact penalty function in the master program. We find that under certain conditions every accumulation point of a sequence of points generated by the algorithm is an optimal solution to the recourse constrained stochastic program, with probability 1. This algorithm is tested on several operations research problems.en_US
dc.typetexten_US
dc.typeDissertation-Reproduction (electronic)en_US
dc.subjectDissertations, Academicen_US
dc.subjectOperations researchen_US
dc.subjectStochastic programming.en_US
thesis.degree.namePh.D.en_US
thesis.degree.leveldoctoralen_US
thesis.degree.disciplineSystems and Industrial Engineeringen_US
thesis.degree.disciplineGraduate Collegeen_US
thesis.degree.grantorUniversity of Arizonaen_US
dc.contributor.advisorHigle, Julia L.en_US
dc.contributor.committeememberSen, Suvrajeeten_US
dc.contributor.committeememberSzidarovszky, Ferencen_US
dc.contributor.committeememberSuchanek, Anaen_US
dc.contributor.committeememberShaked, Mosheen_US
dc.identifier.proquest9121531en_US
dc.identifier.oclc708645914en_US
All Items in UA Campus Repository are protected by copyright, with all rights reserved, unless otherwise indicated.