Stochastic Programming

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

  • Yonghan Feng
  • Jean-Paul Watson
  • Ignacio Rios
  • Sarah M. Ryan
  • Kai Spurkel
  • Roger J.B. Wets
  • David L. Woodruff
    • Categories Stochastic Programming

    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

  • Kwok Cheung
  • Dinakar Gade
  • Cesar Silva-Monroy
  • Jean-Paul Watson
  • Sarah M. Ryan
  • Roger J.B. Wets
  • David L. Woodruff
    • Categories Stochastic Programming

    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

    Chance-Constrained Multi-Terminal Network Design Problems

  • Yongjia Song
  • Minjiao Zhang
    • Categories Integer Programming, Network Optimization, Stochastic Programming Tags , , ,

    We consider a reliable network design problem under uncertain edge failures. Our goal is to select a minimum-cost subset of edges in the network to connect multiple terminals together with high probability. This problem can be seen as a stochastic variant of the Steiner tree problem. We propose a scenario-based Steiner cut formulation, and a … Read more

    Improving the integer L-shaped method

  • Shabbir Ahmed
  • Gustavo Angulo
  • Santanu S. Dey
    • Categories Integer Programming, Stochastic Programming Tags , , ,

    We consider the integer L-shaped method for two-stage stochastic integer programs. To improve the performance of the algorithm, we present and combine two strategies. First, to avoid time-consuming exact evaluations of the second-stage cost function, we propose a simple modification that alternates between linear and mixed-integer subproblems. Then, to better approximate the shape of the … Read more

    Stochastic Quasi-Fejér Block-Coordinate Fixed Point Iterations with Random Sweeping

  • Patrick L. Combettes
  • Jean-Christophe Pesquet
    • Categories Convex Optimization, Nonsmooth Optimization, Stochastic Programming Tags , , , , , , ,

    This work investigates the properties of stochastic quasi-Fejér monotone sequences in Hilbert spaces and emphasizes their pertinence in the study of the convergence of block-coordinate fixed point methods. The iterative methods under investigation feature random sweeping rules to select the blocks of variables that are activated over the course of the iterations and allow for … Read more

    Validating Sample Average Approximation Solutions with Negatively Dependent Batches

  • Jiajie Chen
  • Cong Han Lim
  • Jeff Linderoth
  • Peter Qian
  • Stephen Wright
    • Categories Stochastic Programming

    Sample-average approximations (SAA) are a practical means of finding approximate solutions of stochastic programming problems involving an extremely large (or infinite) number of scenarios. SAA can also be used to find estimates of a lower bound on the optimal objective value of the true problem which, when coupled with an upper bound, provides confidence intervals … Read more

    Chance Constrained Mixed Integer Program: Bilinear and Linear Formulations, and Benders Decomposition

  • Yu An
  • Bo Zeng
  • Ludwig Kuznia
    • Categories Integer Programming, Stochastic Programming Tags , , , , ,

    In this paper, we study chance constrained mixed integer program with consideration of recourse decisions and their incurred cost, developed on a finite discrete scenario set. Through studying a non-traditional bilinear mixed integer formulation, we derive its linear counterparts and show that they could be stronger than existing linear formulations. We also develop a variant … Read more

    Direct search based on probabilistic descent

  • Serge Gratton
  • Clément W. Royer
  • Luis Nunes Vicente
  • Z. Zhang
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization, Stochastic Programming Tags , , , , ,

    Direct-search methods are a class of popular derivative-free algorithms characterized by evaluating the objective function using a step size and a number of (polling) directions. When applied to the minimization of smooth functions, the polling directions are typically taken from positive spanning sets which in turn must have at least n+1 vectors in an n-dimensional … Read more

    A Proximal Stochastic Gradient Method with Progressive Variance Reduction

  • Lin Xiao
  • Tong Zhang
    • Categories Convex and Nonsmooth Optimization, Stochastic Programming Tags , ,

    We consider the problem of minimizing the sum of two convex functions: one is the average of a large number of smooth component functions, and the other is a general convex function that admits a simple proximal mapping. We assume the whole objective function is strongly convex. Such problems often arise in machine learning, known … Read more

    An Improved Stochastic Optimization Model for Water Supply Pumping Systems in Urban Networks

  • Douglas Alem
  • Jonathan De La Vega
    • Categories Applications - OR and Management Sciences, Stochastic Programming Tags , ,

    This study investigates a pump scheduling problem for the collection, transfer and storage of water in water supply systems in urban networks. The objective of this study is to determine a method to minimize the electricity costs associated with pumping operations. To address the dynamic and random nature of water demand, we propose a two-stage … Read more