Search

We introduce an aggregation framework to address multi-stage stochastic programs with mixed-integer state variables and continuous local variables (MSILPs). Our aggregation framework imposes additional structure to the integer state variables by leveraging the information of the underlying stochastic process, which is modeled as a Markov chain (MC). We demonstrate that the aggregated MSILP can be solved exactly via a branch-and-cut algorithm integrated with a variant of stochastic dual dynamic programming. To improve tractability, we propose to use this approach to obtain dual bounds. Moreover, we apply two-stage linear decision rule (2SLDR) approximations, in particular a new MC-based variant that we propose, to obtain high-quality decision policies with significantly reduced computational effort. We test the proposed methodologies in an MSILP model for hurricane disaster relief logistics planning. Our empirical evaluation compares the effectiveness of the various proposed approaches and analyzes the trade-offs between policy flexibility, solution quality, and computational effort. Specifically, the 2SLDR approximation yields provable high-quality solutions for our test instances supported by the proposed bounding procedure. We also extract valuable managerial insights from the solution behaviors exhibited by the underlying decision policies.

We consider a logistics planning problem of prepositioning relief items in preparation for an impending hurricane landfall. This problem is modeled as a multiperiod network flow problem where the objective is to minimize the logistics cost of operating the network and the penalty for unsatisfied demand. We assume that the demand for relief items can be derived from the hurricane's predicted intensity and landfall location, which evolves according to a Markov chain. We consider this problem in two different settings, depending on whether the time of landfall is assumed to be deterministic (and known a priori) or random. For the former case, we introduce a fully adaptive multi-stage stochastic programming (MSP) model that allows the decision-maker to adjust the prepositioning decisions, sequentially, over multiple stages, as the hurricane's characteristics become clearer. For the latter case, we extend the MSP model with a random number of stages introduced in Guigues (2021), to the case where the underlying stochastic process is assumed to be stage-wise dependent. We benchmark the performance of the MSP models with other approximation policies such as the static and rolling-horizon two-stage stochastic programming approaches. Our numerical results provide key insight into the value of MSP, in disaster relief logistics planning.

Variations of physical and chemical characteristics of biomass reduce equipment utilization and increase operational costs of biomass processing. Biomass processing facilities use sensors to monitor the changes in biomass characteristics. Integrating sensory data into the operational decisions in biomass processing will increase its flexibility to the changing biomass conditions. In this paper, we propose a multi-stage stochastic programming model that minimizes the expected operational costs by identifying the initial inventory level and creating an operational decision policy for equipment speed settings. These policies take the sensory information data and the current biomass inventory level as inputs to dynamically adjust inventory levels and equipment settings according to the changes in the biomass' characteristics. We ensure that a prescribed target reactor utilization is consistently achieved by penalizing the violation of the target reactor feeding rate. A case study is developed using real-world data collected at Idaho National Laboratory's biomass processing facility. We show the value of multi-stage stochastic programming from an extensive computational experiment. Our sensitivity analysis indicates that updating the infeed rate of the system, the processing speed of equipment, and bale sequencing based on the moisture level of biomass improves the processing rate of the reactor and reduces operating costs., Comment: 26 pages, 5 figures

Multistage Stochastic Programming (MSP) is a class of models for sequential decision-making under uncertainty. MSP problems are known for their computational intractability due to the sequential nature of the decision-making structure and the uncertainty in the problem data due to the so-called curse of dimensionality. A common approach to tackle MSP problems with a large number of stages is a rolling-horizon (RH) procedure, where one solves a sequence of MSP problems with a smaller number of stages. This leads to a delicate issue of how many stages to include in the smaller problems used in the RH procedure. This paper addresses this question for, both, finite and infinite horizon MSP problems. For the infinite horizon case with discounted costs, we derive a bound which can be used to prescribe an epsilon-sufficient number of stages. For the finite horizon case, we propose a heuristic approach from the perspective of approximate dynamic programming to provide a sufficient number of stages for each roll in the RH procedure. Our numerical experiments on a hydrothermal power generation planning problem show the effectiveness of the proposed approaches.

Variations of physical and chemical characteristics of biomass lead to an uneven flow of biomass in a biorefinery, which reduces equipment utilization and increases operational costs. Uncertainty of biomass supply and high processing costs increase the risk of investing in the US's cellulosic biofuel industry. We propose a stochastic programming model to streamline processes within a biorefinery. A chance constraint models system's reliability requirement that the reactor is operating at a high utilization rate given uncertain biomass moisture content, particle size distribution, and equipment failure. The model identifies operating conditions of equipment and inventory level to maintain a continuous flow of biomass to the reactor. The Sample Average Approximation method approximates the chance constraint and a bisection search-based heuristic solves this approximation. A case study is developed using real-life data collected at Idaho National Laboratory's pilot biomass processing facility. An extensive computational analysis indicates that sequencing of biomass bales based on moisture level, increasing storage capacity, and managing particle size distribution increase utilization of the reactor and reduce operational costs.

We present adaptive sequential SAA (sample average approximation) algorithms to solve large-scale two-stage stochastic linear programs. The iterative algorithm framework we propose is organized into \emph{outer} and \emph{inner} iterations as follows: during each outer iteration, a sample-path problem is implicitly generated using a sample of observations or ``scenarios," and solved only \emph{imprecisely}, to within a tolerance that is chosen \emph{adaptively}, by balancing the estimated statistical error against solution error. The solutions from prior iterations serve as \emph{warm starts} to aid efficient solution of the (piecewise linear convex) sample-path optimization problems generated on subsequent iterations. The generated scenarios can be independent and identically distributed (iid), or dependent, as in Monte Carlo generation using Latin-hypercube sampling, antithetic variates, or randomized quasi-Monte Carlo. We first characterize the almost-sure convergence (and convergence in mean) of the optimality gap and the distance of the generated stochastic iterates to the true solution set. We then characterize the corresponding iteration complexity and work complexity rates as a function of the sample size schedule, demonstrating that the best achievable work complexity rate is Monte Carlo canonical and analogous to the generic $\mathcal{O}(\epsilon^{-2})$ optimal complexity for non-smooth convex optimization. We report extensive numerical tests that indicate favorable performance, due primarily to the use of a sequential framework with an optimal sample size schedule, and the use of warm starts. The proposed algorithm can be stopped in finite-time to return a solution endowed with a probabilistic guarantee on quality.

In the aftermath of a hurricane, humanitarian logistics plays a critical role in delivering relief items to the affected areas in a timely fashion. This paper proposes a novel stochastic lookahead framework that implements a two-stage stochastic programming model in a rolling horizon fashion to address the evolving uncertain logistics system state during the post-hurricane humanitarian logistics operations. The two-stage stochastic programming model that executes in this rolling horizon framework is formulated as a mixed-integer programming problem. The model aims to minimize the sum of transportation and social costs. The social cost is measured as a function of deprivation for unsatisfied demand. Our extensive numerical experiment results and sensitivity analysis demonstrate the effectiveness of the proposed approach in reducing the total cost incurred during the post-hurricane relief logistics operations compared to the two-stage stochastic programming model implemented in a static approach.

Significant evidence has become available that emphasizes the importance of personalization in medicine. In fact, it has become a common belief that personalized medicine is the future of medicine. The core of personalized medicine is the ability to design clinical trials that investigate the role of patient covariates on treatment effects. In this work, we study the optimal design of two-armed clinical trials to maximize accuracy of statistical models where the interaction between patient covariates and treatment effect are incorporated to enable precision medication. Such a modeling extension leads to significant complexities for the produced optimization problems because they include optimization over design and covariates concurrently. We take a robust optimization approach and minimize (over design) the maximum (over population) variance of interaction effect between treatment and patient covariates. This results in a min-max bi-level mixed integer nonlinear programming problem, which is notably challenging to solve. To address this challenge, we introduce a surrogate model by approximating the objective function for which we propose two solution approaches. The first approach provides an exact solution based on reformulation and decomposition techniques. In the second approach, we provide a lower bound for the inner optimization problem and solve the outer optimization problem over the lower bound. We test our proposed algorithms with synthetic and real-world data sets and compare it with standard (re-)randomization methods. Our numerical analysis suggests that the lower bounding approach provides high-quality solutions across a variety of settings.

The multi-vehicle covering tour problem with time windows (MCTPTW) aims to construct a set of maximal coverage routes for a fleet of vehicles that serve (observe) a secondary set of sites given a fixed time schedule, coverage requirements, and energy restrictions. The problem is formulated as a mixed-integer second-order cone programming (MISOCP) model and is an extension of both the multi-covering tour problem and the vehicle routing problem with time windows under energy constraints. Further, we study a special case of the proposed model and develop a labeling algorithm to solve its Lagrangian relaxation problem, which exploits the combinatorial structure exhibited by an optimal solution to the Lagrangian relaxation., Comment: 37 pages, 7 figures, 6 tables

In this paper, we extend the adaptive partition-based approach for solving two-stage stochastic programs with fixed recourse to the multistage stochastic programming setting. The proposed algorithms integrate the adaptive partition-based strategy with a popular approach for solving multistage stochastic programs, the stochastic dual dynamic programming, via different tree-traversal strategies in order to enhance its computational efficiency. Our numerical experiments on a hydro-thermal power generation planning problem show the effectiveness of the proposed algorithms., Comment: 27 pages, 6 figures

We study the conjugacy approximation method in the context of Bayesian ranking and selection with unknown correlations. Under the assumption of normal-inverse-Wishart prior distribution, the posterior distribution remains a normal-inverse-Wishart distribution thanks to the conjugacy property when all alternatives are sampled at each step. However, this conjugacy property no longer holds if only one alternative is sampled at a time, an appropriate setting when there is a limited budget on the number of samples. We propose two new conjugacy approximation methods based on the idea of moment matching. Both of them yield closed-form Bayesian prior updating formulas. This updating formula can then be combined with the knowledge gradient algorithm under the "value of information" framework. We conduct computational experiments to show the superiority of the proposed conjugacy approximation methods, including applications in wind farm placement and computer model calibration.

Fuel cost contributes to a significant portion of operating cost in cargo transportation. Though classic routing models usually treat fuel cost as input data, fuel consumption heavily depends on the travel speed, which has led to the study of optimizing speeds over a given fixed route. In this paper, we propose a joint routing and speed optimization problem to minimize the total cost, which includes the fuel consumption cost. The only assumption made on the dependence between the fuel cost and travel speed is that it is a strictly convex differentiable function. This problem is very challenging, with medium-sized instances already difficult for a general mixed-integer convex optimization solver. We propose a novel set partitioning formulation and a branch-cut-and-price algorithm to solve this problem. Our algorithm clearly outperforms the off-the-shelf optimization solver, and is able to solve some benchmark instances to optimality for the first time.