Software for data-based stochastic programming using bootstrap estimation

In this paper we describe software for stochastic programming that uses only sampled data to obtain both a consistent sample-average solution and a consistent estimate of confidence intervals for the optimality gap using bootstrap and bagging. The underlying distribution whence the samples come is not required. Article Download View Software for data-based stochastic programming using … Read more

Confidence Interval Software for Multi-stage Stochastic Programs

When the uncertainty is explicitly modeled in an optimization problem, it is often necessary to use samples to compute a solution, which gives rise to a need to compute confidence intervals around the objective function value that is obtained. In this paper we describe software that implements well-known methods for two stage problems and we … Read more

A Parallel Hub-and-Spoke System for Large-Scale Scenario-Based Optimization Under Uncertainty

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

Projective Hedging for Stochastic Programming

We propose a decomposition algorithm for multistage stochastic programming that resembles the progressive hedging method of Rockafellar and Wets, but is provably capable of several forms of asynchronous operation. We derive the method from a class of projective operator splitting methods fairly recently proposed by Combettes and Eckstein, significantly expanding the known applications of those … Read more

The stochastic vehicle routing problem, a literature review, part I: models

Building on the work of Gendreau, Laporte, and Seguin (1996), we review the past 20 years of scientific literature on stochastic vehicle routing problems (SVRP). The numerous variants of the problem that have been studied in the literature are described and categorized. Also a thorough review of solution methods applied to the SVRP is included … Read more

Obtaining Lower Bounds from the Progressive Hedging Algorithm for Stochastic Mixed-Integer Programs

We present a method for computing lower bounds in the Progressive Hedging Algorithm (PHA) for two-stage and multi-stage stochastic mixed-integer programs. Computing lower bounds in the PHA allows one to assess the quality of the solutions generated by the algorithm contemporaneously. The lower bounds can be computed in any iteration of the algorithm by using … Read more

Toward Scalable Stochastic Unit Commitment – Part 1: Load Scenario Generation

Unit commitment decisions made in the day-ahead market and during subsequent reliability assessments are critically based on forecasts of load. Traditional, deterministic unit commitment is based on point or expectation-based load forecasts. In contrast, stochastic unit commitment relies on multiple load scenarios, with associated probabilities, that in aggregate capture the range of likely load time-series. … Read more

Toward Scalable Stochastic Unit Commitment – Part 2: Solver Configuration and Performance Assessment

In this second portion of a two-part analysis of a scalable computational approach to stochastic unit commitment, we focus on solving stochastic mixed-integer programs in tractable run-times. Our solution technique is based on Rockafellar and Wets’ progressive hedging algorithm, a scenario-based decomposition strategy for solving stochastic programs. To achieve high-quality solutions in tractable run-times, we … Read more

PySP: Modeling and Solving Stochastic Programs in Python

Although stochastic programming is a powerful tool for modeling decision-making under uncertainty, various impediments have historically prevented its wide-spread use. One key factor involves the ability of non-specialists to easily express stochastic programming problems as extensions of deterministic models, which are often formulated first. A second key factor relates to the difficulty of solving stochastic … Read more

Python Optimization Modeling Objects (Pyomo)

We describe Pyomo, an open source tool for modeling optimization applications in Python. Pyomo can be used to de fine symbolic problems, create concrete problem instances, and solve these instances with standard solvers. Pyomo provides a capability that is commonly associated with algebraic modeling languages such as AMPL, AIMMS, and GAMS, but Pyomo’s modeling objects are … Read more