Inspired by the retail industry, we introduce a fundamentally new approach towards stochastic inventory routing by replenishing retailers from a central warehouse using a time-based shipment consolidation policy. Such a time-based dispatching policy, where retailers facing stochastic demand are repetitively replenished at fixed times, is essential in practice. It allows for easy incorporation with dependent … Read more
In this paper, we present a sequential sampling-based algorithm for the two-stage distributionally robust linear programming (2-DRLP) models. The 2-DRLP models are defined over a general class of ambiguity sets with discrete or continuous probability distributions. The algorithm is a distributionally robust version of the well-known stochastic decomposition algorithm of Higle and Sen (Math. of … Read more
We present JuDGE.jl, an open-source Julia package for solving multistage stochastic capacity expansion problems using Dantzig-Wolfe decomposition. Models for JuDGE.jl are built using JuMP, the algebraic modelling language in Julia, and solved by repeatedly applying mixed-integer programming. We illustrate JuDGE.jl by formulating and solving a toy knapsack problem, and demonstrate the performance of JuDGE.jl on … Read more
Efficient solution of stochastic programming problems generally requires the use of parallel computing resources. Here, we describe the open source package mpi-sppy, in which efficient and scalable parallelization is a central feature. We describe the overall architecture and provide computational examples and results showing scalability to the largest instances that we know of for the … Read more
Distributionally robust optimization (DRO) is a mathematical framework to incorporate ambiguity over the actual data-generating probability distribution. Data-driven DRO problems based on the Wasserstein distance are of particular interest for their sound mathematical properties. For right-hand-sided uncertainty, however, existing methods rely on dual vertex enumeration rendering the problem intractable in practical applications. In this context, … Read more
This paper presents a novel algorithmic study and complexity analysis of distributionally robust multistage convex optimization (DR-MCO). We propose a new class of algorithms for solving DR-MCO, namely a sequential dual dynamic programming (Seq-DDP) algorithm and its nonsequential version (NDDP). The new algorithms generalize and strengthen existing DDP-type algorithms by introducing the technique of regularization … Read more
We propose a statistically optimal approach to construct data-driven decisions for stochastic optimization problems. Fundamentally, a data-driven decision is simply a function that maps the available training data to a feasible action. It can always be expressed as the minimizer of a surrogate optimization model constructed from the data. The quality of a data-driven decision … Read more
We study decomposition algorithms for risk-averse multistage stochastic programs with expected conditional risk measures (ECRMs). ECRMs are attractive because they are time-consistent, which means that a plan made today will not be changed in the future if the problem is re-solved given a realization of the random variables. We show that solving risk-averse problems based … Read more
We consider the (single-stage) stochastic bin packing problem (SBPP) which is based on a given list of items the sizes of which are represented by stochastically independent random variables. The SBPP requires to determine the minimum number of unit capacity bins needed to pack all the items, such that for each bin the probability of … Read more
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 … Read more