Supply chain network design (SCND) identifies the production and distribution resources essential to maximizing a network’s profit. Once implemented, a SCND impacts a network’s performance for the long-term. This dissertation extends the SCND literature both in terms of model scope and solution approach. The SCND problem can be more realistically modeled to improve design decisions by including: the location, capacity, and technology attributes of a resource; the effect of the economies of scale on the cost structure; multiple products and multiple levels of supply chain hierarchy; stochastic, dynamic, and correlated demand; and the gradually unfolding uncertainty. The resulting multistage stochastic mixed-integer program (MSMIP) has no known general purpose solution methodology. Two decomposition approaches—end-of-horizon (EoH) decomposition and nodal decomposition—are applied. The developed EoH decomposition exploits the traditional treatment of the end-of-horizon effect. It rests on independently optimizing the SCND of every node of the last level of the scenario-tree. Imposing these optimal configurations before optimizing the design decisions of the remaining nodes produces a smaller and thus easier to solve MSMIP. An optimal solution results when the discount rate is 0 percent. Otherwise, this decomposition deduces a bound on the optimality-gap. This decomposition is neither SCND nor MSMIP specific; it pertains to any application sensitive to the EoH-effect and to special cases of MSMIP. To demonstrate this versatility, additional computational experiments for a two-stage mixed-integer stochastic program (SMIP) are included. This dissertation also presents the first application of nodal decomposition in both SCND and MSMIP. The developed column generation heuristic optimizes the nodal sub-problems using an iterative procedure that provides a restricted master problem’s columns. The heuristic’s computational efficiency rests on solving the sub-problems independently and on its novel handling of the master problem. Conceptually, it reformulates the master problem to avoid the duality-gap. Technologically, it provides the first application of Leontief substitution flow problems in MSMIP and thereby shows that hypergraphs lend themselves to loosely coupled MSMIPs. Computational results demonstrate superior performance of the heuristic approach and also show how this heuristic still applies when the SCND problem is modeled as a SMIP where the restricted master problem is a shortest-path problem.

We consider joint chance-constrained programs with random lefthand sides. The motivation of this project is that this class of problem has many important applications, but there are few existing solution methods. For the most part, we deal with the subclass of problems for which the underlying parameter distributions are discrete. This assumption allows the original problem to be formulated as a deterministic equivalent mixed-integer program. We rst approach the problem as a mixed-integer program and derive a class of optimality cuts based on irreducibly infeasible subsets of the constraints of the scenarios of the problem. The IIS cuts can be computed effciently by means of a linear program. We give a method for improving the upper bound of the problem when no IIS cut can be identifi ed. We also give an implementation of an algorithm incorporating these ideas and finish with some computational results. We present a tabu search metaheuristic for fi nding good feasible solutions to the mixed-integer formulation of the problem. Our heuristic works by de ning a sufficient set of scenarios with the characteristic that all other scenarios do not have to be considered when generating upper bounds. We then use tabu search on the one-opt neighborhood of the problem. We give computational results that show our metaheuristic outperforming the state-of-the-art industrial solvers. We then show how to reformulate the problem so that the chance-constraints are monotonic functions. We then derive a convergent global branch-and-bound algorithm using the principles of monotonic optimization. We give a finitely convergent modi cation of the algorithm. Finally, we give a discussion on why this algorithm is computationally ine ffective. The last section of this dissertation details an application of joint chance-constrained stochastic programs to a vaccination allocation problem. We show why it is necessary to formulate the problem with random parameters and also why chance-constraints are a good framework for de fining an optimal policy. We give an example of the problem formulated as a chance constraint and a short numerical example to illustrate the concepts.

This research addresses the infrastructure maintenance scheduling problems under budget uncertainty. Infrastructure agencies usually face budget uncertainties that will eventually lead to suboptimal planning if maintenance decisions are made without taking the uncertainty into consideration. It is important for decision makers to adopt maintenance scheduling policies that take future budget uncertainty into consideration. The author proposes a multistage, stochastic linear programming model to address this problem. The author also develops solution procedures using the augmented Lagrangian decomposition algorithm and scenario reduction method. A case study exploring the computational characteristics of the proposed methods is conducted and the benefit of using the stochastic programming approach is discussed. In the case study, the road network in Dallas District is used with data taken from the Texas Department of Transportation’s Pavement Management Information System. The case study results reveal that the stochastic programming solutions tend to allocate more resources to preventive maintenance than deterministic solutions that ignore the uncertainty information. The proposed methodology can help decision makers effectively obtain optimal maintenance plan under budget uncertainty. / text

Any decentralized retail or wholesale system of competing entities requires a benefit sharing arrangement when competing entities collaborate after their demands are realized. For instance, consider a distribution system similar to the observed behavior of independent car dealerships. If a dealership does not have in stock the car requested by a customer, it might consider acquiring it from a competing dealer. Such behavior raises questions about competitive procurement strategies that achieve system optimal outcomes. This dissertation consists of three main bodies of work contained respectively in chapters 2, 3, and 4. In the first work -- chapter 2, we examine a decentralized system that adopts an ex-post agreed transfer payment approach proposed by Anupindi et al. (Manuf. Serv. Oper.Manag. 4(3):349-368, 2001). In particular, we state a set of conditions on cost parameters and distributions that guarantee uniqueness of pure strategy Nash equilibrium. In the second work -- chapter 3, we introduce a multilevel graph framework that links decentralized inventory distribution models as a network of stochastic programming with recourse problems. This framework depicts independent retailers who maximize their individual expected profits, with each retailer independently procuring inventory in the ex-ante stage in response to forecasted demand and anticipated cooperative recourse action of all retailers in the system. The graph framework clarifies the modeling connection between problems in a taxonomy of decentralized inventory distribution models. This unifying perspective links the past work and shades light on future research directions. In the last work -- chapter 4, we examine and recast the biform games modeling framework as two-stage stochastic programming with recourse. Biform games modeling framework addresses two-stage games with competitive first stage and cooperative second stage without ex-ante agreement on profit sharing scheme. The two-stage stochastic programming view of biform games is demonstrated on examples from all the known examples regarding operational decision problems of competing firms from the literature. It allows an “old” mathematical methodology to showcase its versatility in modeling combined competitive and cooperative game options. In short, this dissertation provides important insights, clarifications, and strategic limitations regarding collaborations in decentralized distribution system.

The development of infectious disease models remains important to provide scientists with tools to better understand disease dynamics and develop more effective control strategies. In this work we focus on the estimation of seasonally varying transmission parameters in infectious disease models from real measles case data. We formulate both discrete-time and continuous-time models and discussed the benefits and shortcomings of both types of models. Additionally, this work demonstrates the flexibility inherent in large-scale nonlinear programming techniques and the ability of these techniques to efficiently estimate transmission parameters even in very large-scale problems. This computational efficiency and flexibility opens the door for investigating many alternative model formulations and encourages use of these techniques for estimation of larger, more complex models like those with age-dependent dynamics, more complex compartment models, and spatially distributed data. How- ever, the size of these problems can become excessively large even for these powerful estimation techniques, and parallel estimation strategies must be explored. Two parallel decomposition approaches are presented that exploited scenario based de- composition and decomposition in time. These approaches show promise for certain types of estimation problems.

Problems with storm water runoff are becoming more frequent, and the main cause is the increase of impervious cover (IC). The imperviousness increases stream peak flows, changes peak times, and so changes the flood distribution. Several policies are used to manage flows and flooding; however most have been reported to be inefficient because land owners do not have correct exposure to price incentives and risk. The main contributions of this thesis are an investigation into market mechanisms to price and allocate impervious cover allowances, while managing flood distribution. The market mechanisms are based on the electricity and gas markets which use linear programming formulations. This thesis develops three net pool market mechanisms: Det_MarketIC is a capped and deterministic market for IC, and Sto_MarketIC and Sto_MarketIC_Risk are stochastic market models with flood component penalties and risk positions representing the desired risk from the community respectively. Additionally, a gross pool market was extended under rainfall uncertainty, Gross_MarketIC. The market design is an auction system with operational constraints and bids for IC allowances from participants. The system relates physical routed flows at nodal or control points to these bids. The models clear the market by creating a demand (supply) curve for increments (reductions) in flows at specific places, and accounts for marginal changes in the expected flood damage and flood damage components. The market formulations estimate efficient allocations and prices. Decomposed prices from the market models are shown based on duality, as applied in electricity markets. The dual prices show spatial and temporal effects of flows, which impact at flooding areas. With Sto_MarketIC and Gross_MarketIC, prices account for changes in flood distribution. With Sto_MarketIC_Risk, prices also account for the risk as CVaR in flooding areas. Thus, prices increase as binding risk conditions are tightened. Finally, the net pool models are illustrated using hydrological and hydraulic simulators based on a small catchment located in Canterbury, New Zealand. Allocations and prices varied with the different models. Participants would face increasing prices in their IC allowances due to increments in flood damage.

This thesis applies a stochastic programming approach to the techno-economic analysis of a wind farm coupled with a pumped storage facility. The production of an optimal day-ahead generating schedule is considered. Wind forecasts contain an element of random error, and several methods of addressing this uncertainty in the optimization process are compared. The methods include robust and reliability-based design optimization in addition to a combination of both approaches, and results indicate that reliability-based design optimization is best-suited to this particular problem. Based on a set of wind forecast error scenarios and historical data, a probability-weighted forecast wind generation scenario set is developed. Reliability constraints are imposed to meet a minimum of 80% of the generating schedule time intervals. This methodology is applied to a case study on Vancouver Island. Preliminary results show that when compared to the base case of a standalone wind farm on Vancouver Island, a wind farm coupled with pumped storage can prove to be economically competitive with pumped storage capital costs below $1.53 million/MW installed pumped storage capacity and a firm energy price of $130/MWh. / Graduate

Mean-risk stochastic programs model uncertainty by including risk measures in the objective function. This allows for modeling risk averseness for many problems in science and engineering. This dissertation addresses gaps in the literature on stochastic programs with mean-risk objectives. This includes a need for a computational study of the few available algorithms for this class of problems. The study was aimed at implementing and performing an empirical investigation of decomposition algorithms for stochastic linear programs with absolute semideviation (ASD) and quantile deviation (QDEV) as mean-risk measures. Specifically, the goals of the study were to analyze for specific instances how algorithms perform across different levels of risk, investigate the effect of using ASD and QDEV as risk measures, and understand when it is appropriate to use the risk-averse approach over the risk-neutral one. We derive two new subgradient based algorithms for the ASD and QDEV models, respectively. These algorithms are based on decomposing the stochastic program stage-wise and using a single (aggregated) cut in the master program to approximate the mean and deviation terms of the mean-risk objective function. We also consider a variant of each of the algorithms from the literature in which the mean-risk objective function is approximated by separate optimality cuts, one for the mean and one for the deviation term. These algorithms are implemented and applied to standard stochastic programming test instances to study their comparative performance. Both the aggregated cut and separate cut algorithms have comparable computational performance for ASD, while the separate cut algorithm outperforms its aggregate counterpart for QDEV. The computational study also reveals several insights on mean-risk stochastic linear programs. For example, the results show that for most standard test instances the risk-neutral approach is still appropriate. We show that this is the case due to the test instances having random variables with uniform marginal distributions. In contrast, when these distributions are changed to be non-uniform, the risk-averse approach is preferred. The results also show that the QDEV mean-risk measure has broader flexibility than ASD in modeling risk.

In this thesis we study how to solve some nonconvex optimization problems by using methods that capitalize on the success of Linear Programming (LP) based solvers for Mixed Integer Linear Programming (MILP). A common aspect of our solution approaches is the use, development and analysis of small but strong extended LP/MILP formulations and approximations. In the first part of this work we develop an LP based branch-and-bound algorithm for mixed integer conic quadratic programs. The algorithm is based on a lifted polyhedral relaxation of conic quadratic constraints by Ben-Tal and Nemirovski. We test the algorithm on a series of portfolio optimization problems and show that it provides a significant computational advantage. In the second part we study the modeling of a class of disjunctive constraints with a logarithmic number of variables. For specially structured disjunctive constraints we give sufficient conditions for constructing MILP formulations with a number of binary variables and extra constraints that is logarithmic in the number of terms of the disjunction. Using these conditions we introduce formulations with these characteristics for SOS1, SOS2 constraints and piecewise linear functions. We present computational results showing that they can significantly outperform other MILP formulations. In the third part we study the modeling of non-convex piecewise linear functions as MILPs. We review several new and existing MILP formulations for continuous piecewise linear functions with special attention paid to multivariate non-separable functions. We compare these formulations with respect to their theoretical properties and their relative computational performance. In addition, we study the extension of these formulations to lower semicontinuous piecewise linear functions. Finally, in the fourth part we study the strength of MILP formulations for LPs with Probabilistic Constraints. We first study the strength of existing MILP formulations that only considers one row of the probabilistic constraint at a time. We then introduce an extended formulation that considers more than one row of the constraint at a time and use it to computationally compare the relative strength between formulations that consider one and two rows at a time.

Thesis (Ph. D.)--University of Washington, 1997. / Vita. Includes bibliographical references (p. [124]-131).