stochastic programming

On parallelizing dual decomposition in stochastic integer programming

  • Miles Lubin
  • Kipp Martin
  • Burhaneddin Sandikçi
  • Cosmin G. Petra
    • Categories Nonsmooth Optimization, Parallel Algorithms, Stochastic Programming Tags , , , , ,

    For stochastic mixed-integer programs, we revisit the dual decomposition algorithm of Car\o{}e and Schultz from a computational perspective with the aim of its parallelization. We address an important bottleneck of parallel execution by identifying a formulation that permits the parallel solution of the \textit{master} program by using structure-exploiting interior-point solvers. Our results demonstrate the potential … Read more

    Threshold Boolean Form for Joint Probabilistic Constraints with Random Technology Matrix

  • Alexander Kogan
  • Miguel A. Lejeune
    • Categories (Mixed) Integer Nonlinear Programming, Data-Mining, Stochastic Programming Tags , , , , ,

    We develop a new modeling and exact solution method for stochastic programming problems that include a joint probabilistic constraint in which the multirow random technology matrix is discretely distributed. We binarize the probability distribution of the random variables in such a way that we can extract a threshold partially defined Boolean function (pdBf) representing the … Read more

    Dynamic sequencing and cut consolidation for the parallel hybrid-cut nested L-shaped method

  • Achim Koberstein
  • Christian Wolf
    • Categories Optimization Software and Modeling Systems, Stochastic Programming Tags , , ,

    The Nested L-shaped method is used to solve two- and multi-stage linear stochastic programs with recourse, which can have integer variables on the first stage. In this paper we present and evaluate a cut consolidation technique and a dynamic sequencing protocol to accelerate the solution process. Furthermore, we present a parallelized implementation of the algorithm, … Read more

    Computational aspects of risk-averse optimisation in two-stage stochastic models

  • Csaba I. Fábián
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming, Stochastic Programming Tags , , , , ,

    In this paper we argue for aggregated models in decomposition schemes for two-stage stochastic programming problems. We observe that analogous schemes proved effective for single-stage risk-averse problems, and for general linear programming problems. A major drawback of the aggregated approach for two-stage problems is that an aggregated master problem can not contain all the information … Read more

    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