Stochastic Programming

Logarithmic-Barrier Decomposition Interior-Point Methods for Stochastic Linear Optimization in a Hilbert Space

  • Baha Alzalg
    • Categories Infinite Dimensional Optimization, Linear Programming, Stochastic Programming

    Several logarithmic-barrier interior-point methods are now available for solving two-stage stochastic optimization problems with recourse in the finite-dimensional setting. However, despite the genuine need for studying such methods in general spaces, there are no infinite-dimensional analogs of these methods. Inspired by this evident gap in the literature, in this paper, we propose logarithmic-barrier decomposition-based interior-point … Read more

    Identifying Effective Scenarios for Sample Average Approximation

  • Lijian Chen
    • Categories Stochastic Programming Tags

    We introduce a method to improve the tractability of the well-known Sample Average Approximation (SAA) without compromising important theoretical properties, such as convergence in probability and the consistency of an independent and identically distributed (iid) sample. We consider each scenario as a polyhedron of the mix of first-stage and second-stage decision variables. According to John’s … Read more

    Partially observable multistage stochastic programming

  • Oscar Dowson
  • David P. Morton
  • Bernardo K. Pagnoncelli
    • Categories Stochastic Programming

    We propose a class of partially observable multistage stochastic programs and describe an algorithm for solving this class of problems. We provide a Bayesian update of a belief-state vector, extend the stochastic programming formulation to incorporate the belief state, and characterize saddle-function properties of the corresponding cost-to-go function. Our algorithm is a derivative of the … Read more

    An Exact Method for Constrained Maximization of the Conditional Value-at-Risk of a Class of Stochastic Submodular Functions

  • Simge Küçükyavuz
  • Hao-Hsiang Wu
    • Categories Integer Programming, Stochastic Programming

    We consider a class of risk-averse submodular maximization problems (RASM) where the objective is the conditional value-at-risk (CVaR) of a random nondecreasing submodular function at a given risk level. We propose valid inequalities and an exact general method for solving RASM under the assumption that we have an efficient oracle that computes the CVaR of … Read more

    The Value of Limited Flexibility in Service Network Designs

  • Ahmad Baubaid
  • Natashia Boland
  • Martin Savelsbergh
    • Categories Stochastic Programming, Transportation

    Less-than-truckload carriers rely on the consolidation of freight from multiple shippers to achieve economies of scale. Collected freight is routed through a number of transfer terminals at each of which shipments are grouped together for the next leg of their journeys. We study the service network design problem confronted by these carriers. This problem includes … Read more

    Multiscale stochastic programming

  • Martin Glanzer
  • Georg Ch. Pflug
    • Categories Stochastic Programming

    Real-world multistage stochastic optimization problems are often characterized by the fact that the decision maker may take actions only at specific points in time, even if relevant data can be observed much more frequently. In such a case there are not only multiple decision stages present but also several observation periods between consecutive decisions where … Read more

    Robust sample average approximation with small sample sizes

  • Edward Anderson
  • Andrew B. Philpott
    • Categories Robust Optimization, Stochastic Programming

    We consider solving stochastic optimization problems in which we seek to minimize the expected value of an objective function with respect to an unknown distribution of random parameters. Our focus is on models that use sample average approximation (SAA) with small sample sizes. We analyse the out-of-sample performance of solutions obtained by solving a robust … Read more

    Risk Aversion to Parameter Uncertainty in Markov Decision Processes with an Application to Slow-Onset Disaster Relief

  • Simge Küçükyavuz
  • Merve Merakli
    • Categories Integer Programming, Stochastic Programming, Supply Chain Management Tags , , , , ,

    In classical Markov Decision Processes (MDPs), action costs and transition probabilities are assumed to be known, although an accurate estimation of these parameters is often not possible in practice. This study addresses MDPs under cost and transition probability uncertainty and aims to provide a mathematical framework to obtain policies minimizing the risk of high long-term … Read more

    Single cut and multicut SDDP with cut selection for multistage stochastic linear programs: convergence proof and numerical experiments

  • Michelle Bandarra
  • Vincent Guigues
    • Categories Stochastic Programming

    We introduce a variant of Multicut Decomposition Algorithms (MuDA), called CuSMuDA (Cut Selection for Multicut Decomposition Algorithms), for solving multistage stochastic linear programs that incorporates a class of cut selection strategies to choose the most relevant cuts of the approximate recourse functions. This class contains Level 1 and Limited Memory Level 1 cut selection strategies, … Read more

    An Adaptive Sequential Sample Average Approximation Framework for Solving Two-stage Stochastic Programs

  • Raghu Pasupathy
  • Yongjia Song
    • Categories Stochastic Programming Tags , ,

    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 … Read more