DOI
10.17077/etd.lz5powef
Document Type
Dissertation
Date of Degree
Fall 2016
Access Restrictions
Access restricted until 02/23/2020
Degree Name
PhD (Doctor of Philosophy)
Degree In
Applied Mathematical and Computational Sciences
First Advisor
Pavlo Krokhmal
Second Advisor
Samuel Burer
First Committee Member
Ann Campbell
Second Committee Member
Weimin Han
Third Committee Member
David Stewart
Abstract
Network design problems have been prevalent and popular in the operations research community for decades, because of their practical and theoretical significance. Due to the relentless progression of technology and the creative development of intelligent, efficient algorithms, today we are able to efficiently solve or give excellent heuristic solutions to many network design problem instances. The purpose of this work is to thoroughly examine and tackle two classes of highly complex network design problems which find themselves at the cutting edge of modern research.
First we examine the stochastic incremental network design problem. This problem differs from traditional network design problems through the addition of both temporal and stochastic elements. We present a modeling framework for this class of problems, conduct a thorough theoretical analysis of the solution structure, and give insights into solution methods.
Next we introduce the robust network design problem with decision-dependent uncertainties. Traditional stochastic optimization approaches shy away from randomness which is directly influenced by a user's decisions, due to the computational challenges that arise. We present a two-stage stochastic programming framework, noting that the complexity of this class of problems is derived from a highly nonlinear term in the first-stage objective function. This term is due to the decision-dependent nature of the uncertainty. We perform a rigorous computational study in which we implement various solution algorithms which are both exact and heuristic, as well as both well-studied and original.
For each of the two classes of problems examined in our work, we give suggestions for future study and offer insights into effective ways of tackling these problems in practice.
Public Abstract
Networks are omnipresent in our lives. We all depend on electricity from the power grid, talk on cell phones that rely on a telecommunications network, and commute on sprawling interconnected roadways. These networks change over time: additional power lines are extended from electricity substations, new cell phone towers are built, and construction crews expand our roadways. All of these networks experience some form of uncertainty: power outages, loss of cell service, and traffic jams.
The time-variant nature of networks and the uncertainty that is inherent to their operation significantly complicate the process of designing an efficient and effective network. Network design is a well-studied mathematical problem. Some research has taken uncertainties into account, and other studies have considered the fact that networks change over time. However, little research has tackled both of these ideas simultaneously. To address this knowledge gap, we create and discuss new models which can be used to mathematically represent the task of growing networks most efficiently. Additionally, we present solution algorithms which can be implemented on computers to produce the optimal solution to these complex network design problems. Our work can be used in academic and industrial settings to inform network expansion efforts in a more comprehensive way than is accomplished by existing methods.
Keywords
Heuristic, Integer Programming, Network Design, Operations Research, Optimization, Stochastic
Pages
xiii, 182 pages
Bibliography
Includes bibliographical references (pages 175-182).
Copyright
Copyright © 2016 Nathaniel Richmond
Recommended Citation
Richmond, Nathaniel. "On stochastic network design: modeling approaches and solution techniques." PhD (Doctor of Philosophy) thesis, University of Iowa, 2016.
https://doi.org/10.17077/etd.lz5powef