Models and Algorithms for Stochastic Network Design and Flow Problems: Applications in Truckload Procurement Auctions and Renewable Energy.

Abstract

This dissertation presents novel mathematical models and algorithms for stochastic network design and flow (SNDF) problems: the optimal design and flow of a network under uncertainty to meet specific requirements while minimizing expected total cost. The focus of this dissertation is SNDF problems characterized by uncertainties in node supplies and/or demands and in arc capacities and/or costs. SNDF problems often have characteristics that render them difficult to model and computationally challenging to solve, including nonlinearities, probabilistic constraints, and stochastic parameters, all of which lead to large-scale, nonlinear, and discrete models.

The work in this dissertation is motivated by problems in combinatorial truckload procurement auctions (CTPA) and wind farm network design (WFND). We use these two applications both for their own sake, as they present important and computationally challenging practical problems, and as a basis for the development of more general SNDF models and algorithmic approaches.

In studying CTPA, we develop a novel bidding framework, the Implicit Bidding Approach (IBA), that permits the solution of fully-enumerated combinatorial auctions in a single round. Using IBA, we can circumvent the computational challenges of CTPAs by reposing the problem as a polynomially-sized integer multicommodity flow problem.

We then extend our CTPA models to consider network uncertainties and show that the resulting model is a special case of a two-stage multicommodity flow problem (TS-MFP). We develop an efficient decomposition algorithm for solving problems in this class and provide extensive computational results to demonstrate its efficacy.

In WFND, we present the integrated generation- and transmission- expansion planning problem for a network of interconnected wind farms. We develop an efficient decomposition algorithm for solving WFND problems and present computational results to demonstrate its efficacy.

We then extend this model to include a probabilistic constraint on loss-of-load-expectation. We demonstrate that this model is extremely challenging and that direct applications of mathematical programming approaches are not viable. We present a hybrid algorithm, which we called Iterative Test-and-Prune (I-T&P), that leverages mathematical programming to solve a series of easy feasibility problems within a larger meta-search algorithm. Computational results for several test systems demonstrate the efficacy of I-T&P.