two-stage stochastic programming

A conservative convergent solution for continuously distributed two-stage stochastic optimization problems

  • Carlos Gamboa
  • Alexandre Street
  • Davi Valladão
    • Categories Stochastic Programming Tags , ,

    Two-stage stochastic programming is a mathematical framework widely used in real- life applications such as power system operation planning, supply chains, logistics, inventory management, and financial planning. Since most of these problems cannot be solved analytically, decision makers make use of numerical methods to obtain a near-optimal solution. Some applica- tions rely on the implementation … 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

    A Stochastic Programming Approach for Electric Vehicle Charging Network Design

  • Ratna Chinnam
  • Sina Faridimehr
  • Saravanan Venkatachalam
    • Categories Stochastic Programming, Transportation Tags , , ,

    Advantages of electric vehicles (EV) include reduction of greenhouse gas and other emissions, energy security, and fuel economy. The societal benefits of large-scale adoption of EVs cannot be realized without adequate deployment of publicly accessible charging stations. We propose a two-stage stochastic programming model to determine the optimal network of charging stations for a community … Read more

    A Stochastic Programming Approach for Shelter Location and Evacuation Planning

  • Vedat Bayram
  • Hande Yaman
    • Categories Second-Order Cone Programming, Stochastic Programming, Transportation Tags , , , , ,

    Shelter location and traffic allocation decisions are critical for an efficient evacuation plan. In this study, we propose a scenario-based two-stage stochastic evacuation planning model that optimally locates shelter sites and that assigns evacuees to nearest shelters and to shortest paths within a tolerance degree to minimize the expected total evacuation time. Our model considers … Read more

    An Adaptive Partition-based Approach for Solving Two-stage Stochastic Programs with Fixed Recourse

  • James R. Luedtke
  • Yongjia Song
    • Categories Stochastic Programming Tags , ,

    We study an adaptive partition-based approach for solving two-stage stochastic programs with fixed recourse. A partition-based formulation is a relaxation of the original stochastic program, and we study a finitely converging algorithm in which the partition is adaptively adjusted until it yields an optimal solution. A solution guided refinement strategy is developed to refine the … 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

    Decomposition Algorithms for Two-Stage Chance-Constrained Programs

  • Simge Küçükyavuz
  • James R. Luedtke
  • Xiao Liu
    • Categories Branch and Cut Algorithms, Integer Programming, Stochastic Programming Tags , , ,

    We study a class of chance-constrained two-stage stochastic optimization problems where second-stage feasible recourse decisions incur additional cost. In addition, we propose a new model, where “recovery” decisions are made for the infeasible scenarios to obtain feasible solutions to a relaxed second-stage problem. We develop decomposition algorithms with specialized optimality and feasibility cuts to solve … Read more

    Large-scale optimization with the primal-dual column generation method

  • Jacek Gondzio
  • Pedro Munari
  • Pablo Gonzalez-Brevis
    • Categories Convex Optimization, Linear Programming, Optimization Software and Modeling Systems Tags , , , , , ,

    The primal-dual column generation method (PDCGM) is a general-purpose column generation technique that relies on the primal-dual interior point method to solve the restricted master problems. The use of this interior point method variant allows to obtain suboptimal and well-centered dual solutions which naturally stabilizes the column generation. A reduction in the number of calls … Read more

    Convergence Analysis of a Weighted Barrier Decomposition Algorithm for Two Stage Stochastic Programming

  • Sanjay Mehrotra
  • M. Gokhan Ozevin
    • Categories Linear, Cone and Semidefinite Programming, Stochastic Programming Tags , ,

    Mehrotra and Ozevin computationally found that a weighted primal barrier decomposition algorithm significantly outperforms the barrier decomposition proposed and analyzed in Zhao, and Mehrotra and Ozevin. This paper provides a theoretical foundation for the weighted barrier decomposition algorithm (WBDA). Although the worst case analysis of the WBDA achieves a first-stage iteration complexity bound that is … Read more

    On complexity of Shmoys – Swamy class of two-stage linear stochastic programming problems

  • Arkadi Nemirovski
  • Alexander Shapiro
    • Categories Approximation Algorithms, Stochastic Programming Tags , ,

    We consider a class of two-stage linear stochastic programming problems, introduced by Shmoys and Swamy (2004), motivated by a relaxation of a stochastic set cover problem. We show that the sample size required to solve this problem by the sample average approximation (SAA) method with a relative accuracy $\kappa>0$ and confidence $1-\alpha$ is polynomial in … Read more