Search

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]

We consider a robust optimization problem in an electric power system under uncertain demand and availability of renewable energy resources. Solving the deterministic alternating current (AC) optimal power flow (ACOPF) problem has been considered challenging since the 1960s due to its nonconvexity. Linear approximation of the AC power flow system sees pervasive use, but does not guarantee a physically feasible system configuration. In recent years, various convex relaxation schemes for the ACOPF problem have been investigated, and under some assumptions, a physically feasible solution can be recovered. Based on these convex relaxations, we construct a robust convex optimization problem with recourse to solve for optimal controllable injections (fossil fuel, nuclear, etc.) in electric power systems under uncertainty (renewable energy generation, demand fluctuation, etc.). We propose a cutting-plane method to solve this robust optimization problem, and we establish convergence and other desirable properties. Experimental results indicate that our robust convex relaxation of the ACOPF problem can provide a tight lower bound. [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]

Following the April 16, 2020 release of the Opening Up America Again guidelines for relaxing coronavirus disease 2019 (COVID- 19) social distancing policies, local leaders are concerned about future pandemic waves and lack robust strategies for tracking and suppressing transmission. Here, we present a strategy for triggering short-term shelter-in-place orders when hospital admissions surpass a threshold. We use stochastic optimization to derive triggers that ensure hospital surges will not exceed local capacity and lockdowns are as short as possible. For example, Austin, Texas— the fastest-growing large city in the United States—has adopted a COVID-19 response strategy based on this method. Assuming that the relaxation of social distancing increases the risk of infection sixfold, the optimal strategy will trigger a total of 135 d (90% prediction interval: 126 d to 141 d) of sheltering, allow schools to open in the fall, and result in an expected 2,929 deaths (90% prediction interval: 2,837 to 3,026) by September 2021, which is 29% of the annual mortality rate. In the months ahead, policy makers are likely to face difficult choices, and the extent of public restraint and cocooning of vulnerable populations may save or cost thousands of lives. [ABSTRACT FROM AUTHOR]

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]

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]

Over the last two decades, coherent risk measures have been well studied as a principled, axiomatic way to characterize the risk of a random variable. Because of this axiomatic approach, coherent risk measures have a number of attractive features for computation, and they have been integrated into a variety of stochastic programming algorithms, including stochastic dual dynamic programming (SDDP), a common class of data-driven solution methods for multistage stochastic programs. Coherent risk measures and SDDP are tools used to manage risk while solving data-driven problems. Perhaps the most prominent example involves informing operations and deriving electricity prices in power systems with significant hydro-electric power, including the Brazilian interconnected power system. We focus on incorporating the more general class of convex risk measures into an SDDP algorithm, exemplifying our approach with the entropic risk measure. It is well-known that coherent risk measures lead to an inconsistency if agents care about their state at the end of the time horizon, but control risk in a stage-wise fashion. The entropic risk measure does not have this shortcoming. We illustrate the advantages of the entropic risk measure with two small examples from transportation and finance, and test the numerical viability of our adaptation of the SDDP decomposition scheme in a large-scale hydro-thermal scheduling problem using data from the Brazilian system. [ABSTRACT FROM AUTHOR]

Economic model predictive control (EMPC) has recently gained popularity for managing energy consumption in buildings that are exposed to non-constant electricity prices, such as time-of-use prices or real-time prices. These electricity prices are employed directly in the objective function of the EMPC problem. This paper considers how electricity prices can be designed in order to achieve a specific objective, which in this case is minimizing peak electricity demand. A primal-dual formulation of the EMPC problem is presented that is used to determine optimal prices that minimize peak demand. The method is demonstrated on a simulated community of 900 residential homes to create a pricing structure that minimizes the peak demand of the community of homes. The pricing structure shows that homes should be given a 1-h peak demand duration, and that the peak prices given to the homes should be spread unevenly across 6 h of the afternoon. [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]

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 stochastic vehicle routing problems on a network with random travel and service times. A fleet of one or more vehicles is available to be routed through the network to service each node. Two versions of the model are developed based on alternative objective functions. We provide bounds on optimal objective function values and conditions under which reductions to simpler models can be made. Our solution method embeds a branch-and-cut scheme within a Monte Carlo sampling-based procedure. [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]

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]

Microgrids are frequently employed in remote regions, in part because access to a larger electric grid is impossible, difficult, or compromises reliability and independence. Although small microgrids often employ spot generation, in which a diesel generator is attached directly to a load, microgrids that combine these individual loads and augment generators with photovoltaic cells and batteries as a distributed energy system are emerging as a safer, less costly alternative. We present a model that seeks the minimum-cost microgrid design and ideal dispatched power to support a small remote site for one year with hourly fidelity under a detailed battery model; this mixed-integer nonlinear program (MINLP) is intractable with commercial solvers but loosely coupled with respect to time. A mixed-integer linear program (MIP) approximates the model, and a partitioning scheme linearizes the bilinear terms. We introduce a novel policy for loosely coupled MIPs in which the system reverts to equivalent conditions at regular time intervals; this separates the problem into subproblems that we solve in parallel. We obtain solutions within 5% of optimality in at most six minutes across 14 MIP instances from the literature and solutions within 5% of optimality to the MINLP instances within 20 minutes. [ABSTRACT FROM AUTHOR]

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]

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]

Vaccines are arguably the most important means of pandemic influenza mitigation. However, as during the 2009 H1N1 pandemic, mass immunization with an effective vaccine may not begin until a pandemic is well underway. In the U.S., state-level public health agencies are responsible for quickly and fairly allocating vaccines as they become available to populations prioritized to receive vaccines. Allocation decisions can be ethically and logistically complex, given several vaccine types in limited and uncertain supply and given competing priority groups with distinct risk profiles and vaccine acceptabilities. We introduce a model for optimizing statewide allocation of multiple vaccine types to multiple priority groups, maximizing equal access. We assume a large fraction of available vaccines are distributed to healthcare providers based on their requests, and then optimize county-level allocation of the remaining doses to achieve equity. We have applied the model to the state of Texas, and incorporated it in a Web-based decision-support tool for the Texas Department of State Health Services (DSHS). Based on vaccine quantities delivered to registered healthcare providers in response to their requests during the 2009 H1N1 pandemic, we find that a relatively small cache of discretionary doses (DSHS reserved 6.8% in 2009) suffices to achieve equity across all counties in Texas. [ABSTRACT FROM AUTHOR]

In preparing for influenza pandemics, public health agencies stockpile critical medical resources. Determining appropriate quantities and locations for such resources can be challenging, given the considerable uncertainty in the timing and severity of future pandemics. We introduce a method for optimizing stockpiles of mechanical ventilators, which are critical for treating hospitalized influenza patients in respiratory failure. As a case study, we consider the US state of Texas during mild, moderate, and severe pandemics. Optimal allocations prioritize local over central storage, even though the latter can be deployed adaptively, on the basis of real-time needs. This prioritization stems from high geographic correlations and the slightly lower treatment success assumed for centrally stockpiled ventilators. We developed our model and analysis in collaboration with academic researchers and a state public health agency and incorporated it into a Web-based decision-support tool for pandemic preparedness and response. [ABSTRACT FROM AUTHOR]

In response to COVID-19, schools across the United States closed in early 2020; many did not fully reopen until late 2021. Although regular testing of asymptomatic students, teachers, and staff can reduce transmission risks, few school systems consistently used proactive testing to safeguard return to classrooms. Socioeconomically diverse public school districts might vary testing levels across campuses to ensure fair, effective use of limited resources. We describe a test allocation approach to reduce overall infections and disparities across school districts. Using a model of SARS-CoV-2 transmission in schools fit to data from a large metropolitan school district in Texas, we reduced incidence between the highest and lowest risk schools from a 5.6-fold difference under proportional test allocation to 1.8-fold difference under our optimized test allocation. This approach provides a roadmap to help school districts deploy proactive testing and mitigate risks of future SARS-CoV-2 variants and other pathogen threats. [ABSTRACT FROM AUTHOR]

This paper introduces a two-stage stochastic program for transmission planning. The model has two dependent random variables, namely, total electric load and available wind power. Given univariate marginal distributions for these two random variables and their correlation coefficient, the joint distribution is modeled using a Gaussian copula. The optimal power flow (OPF) problem is solved based on the linearized direct current (DC) power flow. The Electric Reliability Council of Texas (ERCOT) network model and its load and wind data are used for a test case. A 95% confidence interval is formed on the optimality gap of candidate solutions obtained using a sample average approximation with 200 and 300 samples from the joint distribution of load and wind. [ABSTRACT FROM PUBLISHER]

We provide a data-driven method for optimizing pharmacybased distribution of antiviral drugs during an influenza pandemic in terms of overall access for a target population and apply it to the state of Texas, USA. We found that during the 2009 influenza pandemic, the Texas Department of State Health Services achieved an estimated statewide access of 88% (proportion of population willing to travel to the nearest dispensing point). However, access reached only 34.5% of US postal code (ZIP code) areas containing <1,000 underinsured persons. Optimized distribution networks increased expected access to 91% overall and 60% in hard-to-reach regions, and 2 or 3 major pharmacy chains achieved near maximal coverage in well-populated areas. Independent pharmacies were essential for reaching ZIP code areas containing <1,000 underinsured persons. This model was developed during a collaboration between academic researchers and public health officials and is available as a decision support tool for Texas Department of State Health Services at a Web-based interface. [ABSTRACT FROM AUTHOR]

We consider a multiperiod system operation problem with two conflicting objectives, minimizing cost and risk. Risk stems from uncertain disruptions to the system during operation. Whereas a general model would hedge against disruptions in each time period, we study special cases in which only a modest number of disruptions occur. To optimize for risk, we employ a convex approximation based on constraint sampling. We develop a stratified sampling scheme based on distributional information on the time of disruption. We establish that our scheme yields significant savings in sampling costs--up to an order of magnitude in the number of time periods--over naive sampling. Moreover, in the absence of distributional information, we exhibit a sampling strategy that has comparable performance to optimal stratification. We numerically demonstrate that stratification improves cost over naive sampling, improving the solution's proximity to the efficient frontier of the bicriteria problem. [ABSTRACT FROM AUTHOR]

We introduce and investigate a new type of decision problem related to multiclass fluid networks. Optimization problems arising from fluid networks with known parameters have been studied extensively in the queueing, scheduling, and optimization literature. In this article, we explore the makespan problem in fluid networks, with the assumption that the parameters are known only through a probability distribution. Thus, the decision maker does not have complete knowledge of the parameters in advance. This problem can be formulated as a stochastic nonlinear program. We provide necessary and sufficient feasibility conditions for this class of problems. We also derive a number of other structural results that can be used in developing effective computational procedures for solving stochastic fluid makespan problems. [ABSTRACT FROM AUTHOR]

The article offers information on the development and benefits of a stochastic-optimization model for military sea lift deployment of U.S. cargo ships and cargo. It states that the model optimizes possible attacks on overseas seaports of debarkation (SPOD's) and allied seaports of debarkation (SPOE's). It notes that several optimization models have been developed for sealift deployment such as Theres and Aviles. It also cites simulation as a preferred optimization method for military attacks.

The construction industry in the United States and other parts of the world has been facing several challenges, including a shortage of skilled workers. A review of the relevant body of knowledge indicates that one of the key reasons for this problem is the absence of human resource management strategies for construction workers at project, corporate, regional, or industry levels. This paper addresses the issues of workforce training and allocation on construction projects. It presents a framework to optimize the investment in, and to make the best use of, the available workforce with the intent to reduce project costs and improve schedule performance. A linear program model, entitled the Optimal Workforce Investment Model, is built to provide an optimization-based framework for matching supply and demand of construction labor most efficiently through training, recruitment, and allocation. Given a project schedule or demand profile and the available pool of workers, the suggested model provides human resource managers a combined strategy for training the available workers and hiring additional workers. The input data to the proposed model consists of a certain available labor pool, cost figures for training workers in different skills, the cost of hiring workers, hourly labor wages, and estimates of affinities between the different considered skills. The objective of the model is to minimize labor costs while satisfying project labor demands. Results from application of the model to typical situations are presented, and recommendations for future developments are made. [ABSTRACT FROM AUTHOR]

Multiskilling is a workforce strategy that has been shown to reduce indirect labor costs, improve productivity, and reduce turnover. A multiskilled workforce is one in which the workers possess a range of skills that allow them to participate in more than one work process. In practice, they may work across craft boundaries. The success of multiskilling greatly relies on the foreman's ability to assign workers to appropriate tasks and to compose crews effectively. The foreman assigns tasks to workers according to their knowledge, capabilities, and experience on former projects. This research investigated the mechanics of allocating a multiskilled workforce and developed a linear programming model to help optimize the multiskilled workforce assignment and allocation process in a construction project, or between the projects of one company. It is concluded that the model will be most useful in conditions where full employment does not exist; however, it is also useful for short term allocation decisions. By running the model for various simulated scenarios, additional observations were made. For example, it is concluded that, for a capital project, the benefits of multiskilling are marginal beyond approximately a 20% concentration of multiskilled workers in a project workforce. Benefits to workers themselves become marginal after acquiring competency in two or three crafts. These observations have been confirmed by field experience. Extension of this model to allocation of multifunctional resources, such as construction equipment, should also be possible. [ABSTRACT FROM AUTHOR]