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

Krokhmal, Pavlo

Second Advisor

Burer, Samuel

First Committee Member

Campbell, Ann

Second Committee Member

Han, Weimin

Third Committee Member

Stewart, David

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

Download

Share

COinS