Document Type


Date of Degree

Fall 2016

Access Restrictions

Access restricted until 02/23/2019

Degree Name

PhD (Doctor of Philosophy)

Degree In

Applied Mathematical and Computational Sciences

First Advisor

Pavlo Krokhmal

Second Advisor

Samuel Burer


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.


Heuristic, Integer Programming, Network Design, Operations Research, Optimization, Stochastic


xiii, 182




Copyright © 2016 Nathaniel Richmond

Available for download on Saturday, February 23, 2019