multi-stage stochastic programming

Sampling-based Decomposition Algorithms for Multistage Stochastic Programming

  • Harsha Gangammanavar
    • Categories Stochastic Programming Tags , , ,

    Sampling-based algorithms provide a practical approach to solving large-scale multistage stochastic programs. This chapter presents two alternative approaches to incorporating sampling within multistage stochastic linear programming algorithms. In the first approach, sampling is used to construct a sample average approximation (SAA) of the true multistage program. Subsequently, an optimization step is undertaken using deterministic decomposition … Read more

    Compromise Policy for Multi-stage Stochastic Linear Programming: Variance and Bias Reduction

  • Jiajun Xu
  • Suvrajeet Sen
    • Categories Applications - Science and Engineering, Dynamic Programming, Stochastic Programming Tags , , , , ,

    This paper focuses on algorithms for multi-stage stochastic linear programming (MSLP). We propose an ensemble method named the “compromise policy”, which not only reduces the variance of the function approximation but also reduces the bias of the estimated optimal value. It provides a tight lower bound estimate with a confidence interval. By exploiting parallel computing, … Read more

    Markov Chain-based Policies for Multi-stage Stochastic Integer Linear Programming with an Application to Disaster Relief Logistics

  • Margarita P Castro
  • Merve Bodur
  • Yongjia Song
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming Tags , , , ,

    We introduce an aggregation framework to address multi-stage stochastic programs with mixed-integer state variables and continuous local variables (MSILPs). Our aggregation framework imposes additional structure to the integer state variables by leveraging the information of the underlying stochastic process, which is modeled as a Markov chain (MC). We demonstrate that the aggregated MSILP can be … Read more

    Risk-averse Regret Minimization in Multi-stage Stochastic Programs

  • Mehran Poursoltani
  • Erick Delage
  • Angelos Georghiou
    • Categories Applications - OR and Management Sciences, Robust Optimization, Stochastic Programming Tags , , ,

    Within the context of optimization under uncertainty, a well-known alternative to minimizing expected value or the worst-case scenario consists in minimizing regret. In a multi-stage stochastic programming setting with a discrete probability distribution, we explore the idea of risk-averse regret minimization, where the benchmark policy can only benefit from foreseeing Delta steps into the future. … Read more

    The Value of Coordination in Multi-Market Bidding of Grid Energy Storage

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

    We consider the problem of a storage owner who trades in a multi-settlement electricity market comprising an auction-based day-ahead market and a continuous intraday market. We show in a stylized model that a coordinated policy that reserves capacity for the intraday market is optimal and that the gap to a sequential policy increases with intraday … Read more

    Confidence Interval Software for Multi-stage Stochastic Programs

  • Xiaotie Chen
  • Sylvain Cazaux
  • Brian Knight
  • David L. Woodruff
    • Categories Stochastic Programming Tags , ,

    When the uncertainty is explicitly modeled in an optimization problem, it is often necessary to use samples to compute a solution, which gives rise to a need to compute confidence intervals around the objective function value that is obtained. In this paper we describe software that implements well-known methods for two stage problems and we … Read more

    Distributionally Robust Stochastic Dual Dynamic Programming

  • Daniel Duque
  • David P. Morton
    • Categories Robust Optimization, Stochastic Programming Tags , ,

    We consider a multi-stage stochastic linear program that lends itself to solution by stochastic dual dynamic programming (SDDP). In this context, we consider a distributionally robust variant of the model with a finite number of realizations at each stage. Distributional robustness is with respect to the probability mass function governing these realizations. We describe a … Read more

    Multi-stage Stochastic Programming for Demand Response Optimization

  • Özlem Cavus
  • Hande Yaman
  • Munise Kübra Şahin
    • Categories (Mixed) Integer Nonlinear Programming, Applications - OR and Management Sciences, Stochastic Programming Tags , , ,

    The increase in the energy consumption puts pressure on natural resources and environment and results in a rise in the price of energy. This motivates residents to schedule their energy consumption through demand response mechanism. We propose a multi-stage stochastic programming model to schedule different kinds of electrical appliances under uncertain weather conditions and availability … Read more

    Two-stage Linear Decision Rules for Multi-stage Stochastic Programming

  • Merve Bodur
  • James R. Luedtke
    • Categories Stochastic Programming Tags , ,

    Multi-stage stochastic linear programs (MSLPs) are notoriously hard to solve in general. Linear decision rules (LDRs) yield an approximation of an MSLP by restricting the decisions at each stage to be an affine function of the observed uncertain parameters. Finding an optimal LDR is a static optimization problem that provides an upper bound on the … Read more

    Bulk Ship Fleet Renewal and Deployment under Uncertainty: A Multi-Stage Stochastic Programming Approach

  • Ayse Nur Arslan
  • Dimitri J. Papageorgiou
    • Categories Stochastic Programming, Supply Chain Management, Transportation Tags , , , , ,

    We study a maritime fleet renewal and deployment problem under demand and charter cost uncertainty. A decision-maker for an industrial bulk shipping company must determine a suitable fleet size, mix, and deployment strategy to satisfy stochastic demand over a given planning horizon. She may acquire vessels in two ways: time chartering and voyage chartering. Time … Read more