Search

Inspired by its success for their continuous counterparts, the standard approach to deal with mixed-integer recourse (MIR) models under distributional uncertainty is to use distribu- tionally robust optimization (DRO). We argue, however, that this modeling choice is not always justified since DRO techniques are generally computationally challenging when integer decision variables are involved. That is why we propose an alternative approach for dealing with distributional uncertainty for the special case of simple integer recourse (SIR) models, which is aimed at obtaining models with improved computational tractability. We show that such models can be obtained by pragmatically selecting the uncertainty set. Here, we consider uncertainty sets based on the Wasserstein distance and also on generalized moment conditions. We compare our approach with standard DRO both numerically and theoretically. An important side result of our analysis is the derivation of performance guarantees for convex approximations of SIR models. In contrast to the literature, these error bounds are not only valid for a continuous distribution but hold for any distribution. [ABSTRACT FROM AUTHOR]

Hurricanes can cause severe property damage and casualties in coastal regions. Diesel fuel plays a crucial role in hurricane disaster relief. It is important to optimize fuel supply chain operations so that emergency diesel fuel demand for power generation in a hurricane's immediate aftermath can be mitigated. It can be challenging to estimate diesel fuel demand and make informed decisions in the distribution process, accounting for the hurricane's path and severity. We develop predictive and prescriptive models to guide diesel fuel supply chain operations for hurricane disaster relief. We estimate diesel fuel demand from historical weather forecasts and power outage data. This predictive model feeds a prescriptive stochastic programming model implemented in a rolling-horizon fashion to dispatch tank trucks. This data-driven optimization tool provides a framework for decision support in preparation for approaching hurricanes, and our numerical results provide insights regarding key aspects of operations. [ABSTRACT FROM AUTHOR]

In this paper, we consider an optimization problem involving crashing an activity network under a single disruption. A disruption is an event whose magnitude and timing are random. When a disruption occurs, the duration of an activity that has yet to start—or alternatively, yet to complete—can change. We formulate a two-stage stochastic mixed-integer program, in which the timing of the stage is random. In our model, the recourse problem is a mixed-integer program. We prove the problem is NP-hard, and using simple examples, we illustrate properties that differ from the problem's deterministic counterpart. Obtaining a reasonably tight optimality gap can require a large number of samples in a sample average approximation, leading to large-scale instances that are computationally expensive to solve. Therefore, we develop a branch-and-cut decomposition algorithm, in which spatial branching of the first stage continuous variables and linear programming approximations for the recourse problem are sequentially tightened. We test our decomposition algorithm with multiple improvements and show it can significantly reduce solution time over solving the problem directly. [ABSTRACT FROM AUTHOR]

Distributionally robust optimization is a popular modeling paradigm in which the underlying distribution of the random parameters in a stochastic optimization model is unknown. Therefore, hedging against a range of distributions, properly characterized in an ambiguity set, is of interest. We study two-stage stochastic programs with linear recourse in the context of distributional ambiguity, and formulate several distributionally robust models that vary in how the ambiguity set is built. We focus on the Wasserstein distance under a p-norm, and an extension, an optimal quadratic transport distance, as mechanisms to construct the set of probability distributions, allowing the support of the random variables to be a continuous space. We study both unbounded and bounded support sets, and provide guidance regarding which models are meaningful in the sense of yielding robust first-stage decisions. We develop cutting-plane algorithms to solve two classes of problems, and test them on a supply-allocation problem. Our numerical experiments provide further evidence as to what type of problems benefit the most from a distributionally robust solution. [ABSTRACT FROM AUTHOR]

Dupacová's early work in minimax solutions of stochastic programs [[6], [24]] predated by half a century a recent surge of work in distributionally robust optimization. Two others major lines of Dupacová's research contributions concern scenario generation and scenario reduction [[15]], with precursor work including [[5], [21]], and her work on asymptotics [[10], [23]]. Jitka Dupacová was the first woman vice dean at the Faculty of Mathematics and Physics at Charles University in 1979. Stochastic programming has seen recent advances with far-reaching impact involving risk measures, distributionally robust optimization, and applications in areas ranging from energy and natural resources to economics and finance to statistics and machine learning. [Extracted from the article]

As populations and economies expand in regions with changing climates, demand for water can quickly grow beyond what natural supply can sustain. This paper proposes to mitigate shortages, such as those that occur along the Lower South Platte River in northeastern Colorado, via a three-step approach: (1) create flow data scenarios, which represent a wide array of hydroclimatic outcomes; (2) use an existing simulation model to process these scenarios in order to locate excess supply and unmet demand both spatially and temporally; and (3) minimize the cost of alleviating identified shortages using a new, multiperiod, two-stage stochastic programming model, which determines reservoir location, size, type, and operation over a 50-year time horizon. Results indicate that demand associated with historical and seasonally shifted scenarios can be satisfied, and unmet demand associated with more challenging reduced-mean runoff scenarios can be mitigated substantially. Furthermore, multiple smaller reservoirs are preferred over a single large reservoir to hedge against these uncertainties. [ABSTRACT FROM AUTHOR]

We consider a multistage stochastic linear program that lends itself to solution by stochastic dual dynamic programming (SDDP). In this context, we consider a distributionally robust variant of the model with a finite number of realizations at each stage. Distributional robustness is with respect to the probability mass function governing these realizations. We describe a computationally tractable variant of SDDP to handle this model using the Wasserstein distance to characterize distributional uncertainty. [ABSTRACT FROM AUTHOR]

Package carriers use sophisticated automated sorting facilities to efficiently process inbound packages and sort them to their down line destinations. During each of several daily processing windows, primary sorters perform high level sortation of the packages and direct them to one of several secondary sorters that are then used to segregate the packages by their outbound loading destinations. We examine the problem of assigning package destinations to the secondary sorters in a way that balances the workload in the facility, while incorporating the day-to-day fluctuation in package volumes and adhering to the outbound loading capacities of the various workcenters in the facility. We present a general stochastic modeling framework using chance constraints to balance the flows, and robust constraints to model the capacity limits. We propose and evaluate the performance of three alternative mixed integer nonlinear formulations for the problem and determine which is most effective. Significant improvement in package flow balance and loading capacity robustness is shown for the test sorting facilities by comparing the solutions from the proposed new model to those obtained when ignoring, partially or completely, the stochasticity in the package volumes. [ABSTRACT FROM AUTHOR]

We consider two types of convex approximations of two-stage totally unimodular integer recourse models. Although worst-case error bounds are available for these approximations, their actual performance has not yet been investigated, mainly because this requires solving the original recourse model. In this paper we assess the quality of the approximating solutions using Monte Carlo sampling, or more specifically, using the so-called multiple replications procedure. Based on numerical experiments for an integer newsvendor problem, a fleet allocation and routing problem, and a stochastic activity network investment problem, we conclude that the error bounds are reasonably sharp if the variability of the random parameters in the model is either small or large; otherwise, the actual error of using the convex approximations is much smaller than the error bounds suggest. Moreover, we conclude that the solutions obtained using the convex approximations are good only if the variability of the random parameters is medium to large. In case this variability is small, however, typically sampling methods perform best, even with modest sample sizes. In this sense, the convex approximations and sampling methods can be considered as complementary solution methods. Moreover, as required for our applications, we extend our approach to derive new error bounds dealing with deterministic second-stage side constraints and relatively complete recourse, and perfect dependencies in the right-hand side vector. [ABSTRACT FROM AUTHOR]

We develop a sequential sampling procedure for a class of stochastic programs. We assume that a sequence of feasible solutions with an optimal limit point is given as input to our procedure. Such a sequence can be generated by solving a series of sampling problems with increasing sample size, or it can be found by any other viable method. Our procedure estimates the optimality gap of a candidate solution from this sequence. If the point estimate of the optimality gap is sufficiently small according to our termination criterion, then we stop. Otherwise, we repeat with the next candidate solution from the sequence under an increased sample size. We provide conditions under which this procedure (i) terminates with probability one and (ii) terminates with a solution that has a small optimality gap with a prespecified probability. [ABSTRACT FROM AUTHOR]

This analysis presents a conservation planning framework for decisions under uncertainty and applies it to the Arctic Coastal Plain of Alaska. Uncertainty arises from variable distributional shifts of species’ ranges due to climate change. The planning framework consists of a two-stage optimization model that selects a nominal conservation area network in the first stage and evaluates its performance under the climate scenarios in the second stage. The model is applied to eleven at-risk species in Alaska including the threatened Spectacled Eider and Steller’s Eider sea ducks and the polar bear. The 109th United States Congress and 2008 federal budget proposed opening for oil and gas development the “1002 Area” of the Arctic National Wildlife Refuge, which intersects the Plain. This analysis finds that, if Arctic Alaska experiences 1.5°C of warming by 2040 (as predicted by the Intergovernmental Panel on Climate Change’s A2 scenario), then potential habitat will decrease significantly for eight of these at-risk species, including the polar bear. This analysis also shows that there is synergism between oil and gas development and climate change. For instance, climate change accompanied by no development of the 1002 Area results in an increase of potential habitat for Steller’s Eider. However, if development accompanies climate change, then there is a 20% decrease in that area. Further, this analysis quantifies the tradeoff between development and maintenance of suitable habitat for at-risk species. [Copyright &y& Elsevier]

Hedge funds typically have non-normal return distributions marked by significant positive or negative skewness and high kurtosis. Mean-variance optimization models ignore these higher moments of the return distribution. This article introduces a new stochastic programming model which incorporates Monte Carlo simulation and optimization to examine the effects on the optimal allocation to hedge funds given benchmark related investment objectives such as expected shortfall and semi-variance. The results show that a substantial allocation--approximately 20% to hedge funds is justified. Specifically, the return distributions of portfolios constructed using the stochastic programming model skew to the right relative to those of the optimal mean-variance portfolios, resulting in higher Sortino ratios. [ABSTRACT FROM AUTHOR]

Determining whether a solution is of high quality (optimal or near optimal) is fundamental in optimization theory and algorithms. In this paper, we develop Monte Carlo sampling-based procedures for assessing solution quality in stochastic programs. Quality is defined via the optimality gap and our procedures' output is a confidence interval on this gap. We review a multiple-replications procedure that requires solution of, say, 30 optimization problems and then, we present a result that justifies a computationally simplified single-replication procedure that only requires solving one optimization problem. Even though the single replication procedure is computationally significantly less demanding, the resulting confidence interval might have low coverage probability for small sample sizes for some problems. We provide variants of this procedure that require two replications instead of one and that perform better empirically. We present computational results for a newsvendor problem and for two-stage stochastic linear programs from the literature. We also discuss when the procedures perform well and when they fail, and we propose using ɛ-optimal solutions to strengthen the performance of our procedures. [ABSTRACT FROM AUTHOR]

We consider the problem of bounding the expected value of a linear program (LP) containing random coefficients, with applications to solving two-stage stochastic programs. An upper bound for minimizations is derived from a restriction of an equivalent, penalty-based formulation of the primal stochastic LP, and a lower bound is obtained from a restriction of a reformulation of the dual. Our "restricted-recourse bounds" are more general and more easily computed than most other bounds because random coefficients may appear anywhere in the LP, neither independence nor boundedness of the coefficients is needed, and the bound is computed by solving a single LP or nonlinear program. Analytical examples demonstrate that the new bounds can be stronger than complementary Jensen bounds. (An upper bound is "complementary" to a lower bound, and vice versa). In computational work, we apply the bounds to a two-stage stochastic program for semiconductor manufacturing with uncertain demand and production rates. [ABSTRACT FROM AUTHOR]

Handling uncertainty in natural inflow is an important part of a hydroelectric scheduling model. In a stochastic programming formulation, natural inflow may be modeled as a random vector with known distribution, but the size of the resulting mathematical program can be formidable. Decomposition-based algorithms take advantage of special structure and provide an attractive approach to such problems. We develop an enhanced Benders decomposition algorithm for solving multistage stochastic linear programs. The enhancements include warm start basis selection, preliminary cut generation, the multicut procedure, and decision tree traversing strategies. Computational results are presented for a collection of stochastic hydroelectric scheduling problems. [ABSTRACT FROM AUTHOR]

Monte Carlo sampling-based algorithms hold much promise for solving stochastic programs with many scenarios. A critical component of such algorithms is a stopping criterion to ensure the quality of the solution. In this paper, we develop a stopping rule theory for a class of algorithms that estimate bounds on the optimal objective function value by sampling. We provide rules for selecting sample sizes and terminating the algorithm under which asymptotic validity of confidence intervals for the quality of the proposed solution can be verified. Empirical coverage results are given for a simple example. [ABSTRACT FROM AUTHOR]