stochastic programming

Importance Sampling in Stochastic Programming: A Markov Chain Monte Carlo Approach

  • Ustun Berk
  • Webster Mort
  • Panos Parpas
  • Quang Kha Tran
    • Categories Stochastic Programming Tags , , , ,

    Stochastic programming models are large-scale optimization problems that are used to facilitate decision-making under uncertainty. Optimization algorithms for such problems need to evaluate the expected future costs of current decisions, often referred to as the recourse function. In practice, this calculation is computationally difficult as it requires the evaluation of a multidimensional integral whose integrand … Read more

    Multi-horizon stochastic programming

  • Marte Fodstad
  • Michal Kaut
  • Lars Hellemo
  • Kjetil T. Midthun
  • Asgeir Tomasgard
  • Adrian S. Werner
    • Categories Stochastic Programming Tags , , ,

    Infrastructure-planning models are challenging because of their combination of different time scales: while planning and building the infrastructure involves strategic decisions with time horizons of many years, one needs an operational time scale to get a proper picture of the infrastructure’s performance and profitability. In addition, both the strategic and operational levels are typically subject … Read more

    Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming

  • Saeed Ghadimi
  • Guanghui Lan
    • Categories Convex and Nonsmooth Optimization, Stochastic Programming, Unconstrained Optimization Tags , , , ,

    In this paper, we introduce a new stochastic approximation (SA) type algorithm, namely the randomized stochastic gradient (RSG) method, for solving an important class of nonlinear (possibly nonconvex) stochastic programming (SP) problems. We establish the complexity of this method for computing an approximate stationary point of a nonlinear programming problem. We also show that this … Read more

    On the convergence of decomposition methods for multi-stage stochastic convex programs

  • Pierre Girardeau
  • Vincent Leclère
  • Andrew B. Philpott
    • Categories Convex Optimization, Dynamic Programming, Stochastic Programming Tags , , , ,

    We prove the almost-sure convergence of a class of sampling-based nested decomposition algorithms for multistage stochastic convex programs in which the stage costs are general convex functions of the decisions, and uncertainty is modelled by a scenario tree. As special cases, our results imply the almost-sure convergence of SDDP, CUPPS and DOASA when applied to … Read more

    Stochastic integer programming based algorithms for adaptable open block surgery scheduling

  • Camilo Mancilla
  • Robert H. Storer
    • Categories Applications - OR and Management Sciences, Scheduling, Stochastic Programming Tags , ,

    We develop algorithms for adaptable schedule problems with patient waiting time, surgeon waiting time, OR idle time and overtime costs. Open block surgery scheduling of multiple surgeons operating in multiple operating rooms (ORs) motivates the work. We investigate creating an “adaptable” schedule of surgeries under knowledge that this schedule will change (be rescheduled) during execution … Read more

    Consistency of sample estimates of risk averse stochastic programs

  • Alexander Shapiro
    • Categories Stochastic Programming Tags , , , , ,

    In this paper we study asymptotic consistency of law invariant convex risk measures and the corresponding risk averse stochastic programming problems for independent identically distributed data. Under mild regularity conditions we prove a Law of Large Numbers and epiconvergence of the corresponding statistical estimators. This can be applied in a straight forward way to establishing … Read more

    Complexity of Bilevel Coherent Risk Programming

  • Jonathan Eckstein
    • Categories Stochastic Programming Tags , ,

    This paper considers a bilevel programming approach to applying coherent risk measures to extended two-stage stochastic programming problems. This formulation technique avoids the time-inconsistency issues plaguing naive models and the incomposability issues which cause time-consistent formulations to have complicated, hard-to-explain objective functions. Unfortunately, the analysis here shows that such bilevel formulations, when using the standard … Read more

    The Decision Rule Approach to Optimization under Uncertainty: Methodology and Applications

  • Angelos Georghiou
  • Daniel Kuhn
  • Wolfram Wiesemann
    • Categories Applications - OR and Management Sciences, Robust Optimization Tags , , ,

    Dynamic decision-making under uncertainty has a long and distinguished history in operations research. Due to the curse of dimensionality, solution schemes that naively partition or discretize the support of the random problem parameters are limited to small and medium-sized problems, or they require restrictive modeling assumptions (e.g., absence of recourse actions). In the last few … Read more

    Optimizing Trading Decisions for Hydro Storage Systems using Approximate Dual Dynamic Programming

  • Nils Löhndorf
  • David Wozabal
  • Stefan Minner
    • Categories Applications - OR and Management Sciences, Dynamic Programming, Stochastic Programming Tags , , ,

    We propose a new approach to optimize operations of hydro storage systems with multiple connected reservoirs which participate in wholesale electricity markets. Our formulation integrates short-term intraday with long-term interday decisions. The intraday problem considers bidding decisions as well as storage operation during the day and is formulated as a stochastic program. The interday problem … Read more

    Higher-Order Confidence Intervals for Stochastic Programming using Bootstrapping

  • Mihai Anitescu
  • Cosmin G. Petra
    • Categories Constrained Nonlinear Optimization, Stochastic Programming Tags , ,

    We study the problem of constructing confidence intervals for the optimal value of a stochastic programming problem by using bootstrapping. Bootstrapping is a resampling method used in the statistical inference of unknown parameters for which only a small number of samples can be obtained. One such parameter is the optimal value of a stochastic optimization … Read more