Stochastic Networks: Tractable Approaches for Identifying Strategic Paths

Persistent Link:
http://hdl.handle.net/10150/194439
Title:
Stochastic Networks: Tractable Approaches for Identifying Strategic Paths
Author:
Reich, Daniel
Issue Date:
2009
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:
In Chapter 1, we present a stochastic shortest path problem that we refer to as the Most Likely Path Problem (MLPP). We prove that optimal solutions to the MLPP are composed of optimal subpaths, a property which is essential for solving the classical deterministic shortest path problem. On series-parallel networks, we produce analytical bounds for the probability of the Most Likely Path (MLP), which we compute efficiently via dynamic programming and ordinal optimization.In Chapter 2, we present an algorithm for preprocessing a class of stochastic shortest path problems on directed acyclic networks. Our method significantly increases the utility of many existing frameworks. Given random costs with finite lower and upper bounds on each edge, our algorithm removes edges that cannot be in any optimal solution to the deterministic shortest path problem for any realization of the random costs. Although this problem is NP-complete, our algorithm efficiently preprocesses many edges in a given network and our computational results show that on average only .2% of the edges in the test problems remain unclassified after preprocessing.In Chapter 3, we introduce a methodology for generating scenario trees from independent samples via k-means clustering. The trees are then input into a well-known stochastic optimization model used for operation planning on the Brazilian power system. The dual prices from this model are by contract used in Brazil to determine prices paid to operators of hydroelectric energy plants. Our computational results provide key insights regarding the variability introduced into these dual prices by both the choice of scenario tree topology and by k-means clustering. We show that for sufficiently large scenario trees, the dual prices are quite stable.
Type:
text; Electronic Dissertation
Degree Name:
Ph.D.
Degree Level:
doctoral
Degree Program:
Applied Mathematics; Graduate College
Degree Grantor:
University of Arizona
Advisor:
Lopes, Leo
Committee Chair:
Lopes, Leo

Full metadata record

DC FieldValue Language
dc.language.isoENen_US
dc.titleStochastic Networks: Tractable Approaches for Identifying Strategic Pathsen_US
dc.creatorReich, Danielen_US
dc.contributor.authorReich, Danielen_US
dc.date.issued2009en_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.abstractIn Chapter 1, we present a stochastic shortest path problem that we refer to as the Most Likely Path Problem (MLPP). We prove that optimal solutions to the MLPP are composed of optimal subpaths, a property which is essential for solving the classical deterministic shortest path problem. On series-parallel networks, we produce analytical bounds for the probability of the Most Likely Path (MLP), which we compute efficiently via dynamic programming and ordinal optimization.In Chapter 2, we present an algorithm for preprocessing a class of stochastic shortest path problems on directed acyclic networks. Our method significantly increases the utility of many existing frameworks. Given random costs with finite lower and upper bounds on each edge, our algorithm removes edges that cannot be in any optimal solution to the deterministic shortest path problem for any realization of the random costs. Although this problem is NP-complete, our algorithm efficiently preprocesses many edges in a given network and our computational results show that on average only .2% of the edges in the test problems remain unclassified after preprocessing.In Chapter 3, we introduce a methodology for generating scenario trees from independent samples via k-means clustering. The trees are then input into a well-known stochastic optimization model used for operation planning on the Brazilian power system. The dual prices from this model are by contract used in Brazil to determine prices paid to operators of hydroelectric energy plants. Our computational results provide key insights regarding the variability introduced into these dual prices by both the choice of scenario tree topology and by k-means clustering. We show that for sufficiently large scenario trees, the dual prices are quite stable.en_US
dc.typetexten_US
dc.typeElectronic Dissertationen_US
thesis.degree.namePh.D.en_US
thesis.degree.leveldoctoralen_US
thesis.degree.disciplineApplied Mathematicsen_US
thesis.degree.disciplineGraduate Collegeen_US
thesis.degree.grantorUniversity of Arizonaen_US
dc.contributor.advisorLopes, Leoen_US
dc.contributor.chairLopes, Leoen_US
dc.contributor.committeememberBayraksan, Guzinen_US
dc.contributor.committeememberBrio, Moyseyen_US
dc.contributor.committeememberIndik, Roberten_US
dc.contributor.committeememberKucukyavuz, Simgeen_US
dc.identifier.proquest10237en_US
dc.identifier.oclc659750836en_US
All Items in UA Campus Repository are protected by copyright, with all rights reserved, unless otherwise indicated.