multistage stochastic programming

Stochastic Dual Dynamic Programming for Multistage Stochastic Mixed-Integer Nonlinear Optimization

  • Shixuan Zhang
  • Xu Andy Sun
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization, Stochastic Programming Tags , , ,

    In this paper, we study multistage stochastic mixed-integer nonlinear programs (MS-MINLP). This general class of problems encompasses, as important special cases, multistage stochastic convex optimization with \emph{non-Lipschitz-continuous} value functions and multistage stochastic mixed-integer linear optimization. We develop stochastic dual dynamic programming (SDDP) type algorithms with nested decomposition, deterministic sampling, and stochastic sampling. The key ingredient … Read more

    Stochastic Dynamic Linear Programming: A Sequential Sampling Algorithm for Multistage Stochastic Linear Programming

  • Harsha Gangammanavar
  • Suvrajeet Sen
    • Categories Stochastic Programming Tags , , ,

    Multistage stochastic programming deals with operational and planning problems that involve a sequence of decisions over time while responding to realizations that are uncertain. Algorithms designed to address multistage stochastic linear programming (MSLP) problems often rely upon scenario trees to represent the underlying stochastic process. When this process exhibits stagewise independence, sampling-based techniques, particularly the … Read more

    Gas Storage Valuation in Incomplete Markets

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

    Natural gas storage valuation is an important problem in energy trading, yet most valuation approaches are based on heuristics or ignore that gas markets are incomplete. We propose an exact valuation model for incomplete gas markets based on multistage stochastic programming. Market incompleteness structurally changes the problem of storage valuation and asset backed trading and … Read more

    The Stochastic Multistage Fixed Charge Transportation Problem: Worst-Case Analysis of the Rolling Horizon Approach

  • Luca Bertazzi
  • Francesca Maggioni
    • Categories Stochastic Programming, Supply Chain Management Tags , , ,

    We introduce the Stochastic multistage fixed charge transportation problem in which a producer has to ship an uncertain load to a customer within a deadline. At each time period, a fixed transportation price can be paid to buy a transportation capacity. If the transportation capacity is used, the supplier also pays an uncertain unit transportation … Read more

    A Distributed Interior-Point KKT Solver for Multistage Stochastic Optimization

  • Hübner Jens
  • Martin Schmidt
  • Marc C. Steinbach
    • Categories Finance and Economics, Parallel Algorithms, Stochastic Programming Tags , , , ,

    Multistage stochastic optimization leads to NLPs over scenario trees that become extremely large when many time stages or fine discretizations of the probability space are required. Interior-point methods are well suited for these problems if the arising huge, structured KKT systems can be solved efficiently, for instance, with a large scenario tree but a moderate … Read more

    BOUNDS AND APPROXIMATIONS FOR MULTISTAGE STOCHASTIC PROGRAMS

  • Francesca Maggioni
  • Georg Ch. Pflug
    • Categories Stochastic Programming Tags , , ,

    Consider (typically large) multistage stochastic programs, which are defined on scenario trees as the basic data structure. It is well known that the computational complexity of the solution depends on the size of the tree, which itself increases typically exponentially fast with its height, i.e. the number of decision stages. For this reason approximations which … Read more

    Worst-case-expectation approach to optimization under uncertainty

  • Joari Paulo da Costa
  • Alexander Shapiro
  • Murilo Pereira Soares
  • Wajdi Tekaya
    • Categories Applications - OR and Management Sciences, Robust Optimization, Stochastic Programming Tags , , , , , , , ,

    In this paper we discuss multistage programming with the data process subject to uncertainty. We consider a situation were the data process can be naturally separated into two components, one can be modeled as a random process, with a specified probability distribution, and the other one can be treated from a robust (worst case) point … Read more

    Time consistency of dynamic risk measures

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

    In this paper we discuss time consistency of risk averse multistage stochastic programming problems. We show, in a framework of finite scenario trees, that composition of law invariant coherent risk measures can be law invariant only for the expectation or max-risk measures. CitationPreprintArticleDownload View PDF

    Risk neutral and risk averse Stochastic Dual Dynamic Programming method

  • Joari Paulo da Costa
  • Alexander Shapiro
  • Murilo Pereira Soares
  • Wajdi Tekaya
    • Categories Dynamic Programming, Scheduling, Stochastic Programming Tags , , , , , ,

    In this paper we discuss risk neutral and risk averse approaches to multistage (linear) stochastic programming problems based on the Stochastic Dual Dynamic Programming (SDDP) method. We give a general description of the algorithm and present computational studies related to planning of the Brazilian interconnected power system. Citation ArticleDownload View PDF

    What Multistage Stochastic Programming Can Do for Network Revenue Management

  • Victor DeMiguel
  • Nishant Mishra
    • Categories Airline Optimization, Stochastic Programming Tags , ,

    Airlines must dynamically choose how to allocate their flight capacity to incoming travel demand. Because some passengers take connecting flights, the decisions for all network flights must be made simultaneously. To simplify the decision making process, most practitioners assume demand is deterministic and equal to average demand. We propose a multistage stochastic programming approach that … Read more