Stochastic Programming

An Integrated Car-and-ride Sharing System for Mobilizing Heterogeneous Travelers with Application in Underserved Communities

  • Siqian Shen
  • Miao Yu
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming, Transportation Tags , , , ,

    The fast-growing carsharing and ride-hailing businesses are generating economic benefits and societal impacts in the modern society. However, both have limitation to cover demand from diverse populations, e.g., travelers in low-income, underserved communities. In this paper, we consider two types of travelers: Type~1 who rent shared cars and Type~2 who need shared rides. We propose … Read more

    Data-DrivenWater Allocation under Climate Uncertainty: A Distributionally Robust Approach

  • Güzin Bayraksan
  • David Love
  • Jangho Park
    • Categories Civil and Environmental Engineering, Robust Optimization, Stochastic Programming Tags , , , ,

    This paper investigates the application of techniques from distributionally robust optimization (DRO) to water allocation under future uncertainty. Specifically, we look at a rapidly-developing area of Tucson, Arizona. Tucson, like many arid and semi-arid regions around the world, faces considerable uncertainty in its ability to provide water for its citizens in the future. The main … Read more

    Multistage stochastic programs with a random number of stages: dynamic programming equations, solution methods, and application to portfolio selection

  • Vincent Guigues
    • Categories Finance and Economics, Stochastic Programming

    We introduce the class of multistage stochastic optimization problems with a random number of stages. For such problems, we show how to write dynamic programming equations and detail the Stochastic Dual Dynamic Programming algorithm to solve these equations. Finally, we consider a portfolio selection problem over an optimization period of random duration. For several instances … Read more

    Scenario Reduction for Risk-Averse Stochastic Programs

  • Sebastian Arpon
  • Tito Homem-de-Mello
  • Bernardo K. Pagnoncelli
    • Categories Stochastic Programming

    In this paper we discuss scenario reduction methods for risk-averse stochastic optimization problems. Scenario reduction techniques have received some attention in the literature and are used by practitioners, as such methods allow for an approximation of the random variables in the problem with a moderate number of scenarios, which in turn make the optimization problem … Read more

    A finite ε-convergence algorithm for two-stage convex 0-1 mixed-integer nonlinear stochastic programs with mixed-integer first and second stage variables

  • Ignacio E. Grossmann
  • Can Li
    • Categories Stochastic Programming Tags , , ,

    In this paper, we propose a generalized Benders decomposition-based branch and bound algorithm, GBDBAB, to solve two-stage convex 0-1 mixed-integer nonlinear stochastic programs with mixed-integer variables in both first and second stage decisions. In order to construct the convex hull of the MINLP subproblem for each scenario in closed-form, we first represent each MINLP subproblem … Read more

    On stochastic auctions in risk-averse electricity markets with uncertain supply

  • Ryan Cory-Wright
  • Golbon Zakeri
    • Categories Finance and Economics, Game Theory, Stochastic Programming Tags , , ,

    This paper studies risk in a stochastic auction which facilitates the integration of renewable generation in electricity markets. We model market participants who are risk averse and reflect their risk aversion through coherent risk measures. We uncover a closed-form characterization of a risk-averse generator’s optimal pre-commitment behaviour for a given real-time policy, both with and … Read more

    Bounds in multi-horizon stochastic programs

  • Elisabetta Allevi
  • Francesca Maggioni
  • Asgeir Tomasgard
    • Categories Applications - OR and Management Sciences, Stochastic Programming

    In this paper, we present bounds for multi-horizon stochastic optimization problems, a class of problems introduced in [16] relevant in many industry-life applications tipically involving strategic and operational decisions on two different time scales. After providing three general mathematical formulations of a multi-horizon stochastic program, we extend the definition of the traditional Expected Value problem … Read more

    A Progressive Batching L-BFGS Method for Machine Learning

  • Raghu Bollapragada
  • Jorge Nocedal
  • Hao-Jun Shi
  • Ping Tak Peter Tang
  • Dheevatsa Mudigere
    • Categories Convex Optimization, Nonlinear Optimization, Stochastic Programming Tags , , ,

    The standard L-BFGS method relies on gradient approximations that are not dominated by noise, so that search directions are descent directions, the line search is reliable, and quasi-Newton updating yields useful quadratic models of the objective function. All of this appears to call for a full batch approach, but since small batch sizes give rise … Read more

    Tutorial on risk neutral, distributionally robust and risk averse multistage stochastic programming

  • Alexander Shapiro
    • Categories Robust Optimization, Stochastic Programming Tags , , , , , ,

    In this tutorial we discuss several aspects of modeling and solving multistage stochastic programming problems. In particular we discuss distributionally robust and risk averse approaches to multistage stochastic programming, and the involved concept of time consistency. This tutorial is aimed at presenting a certain point of view of multistage stochastic programming, and can be viewed … Read more

    Stochastic dual dynamic programming with stagewise dependent objective uncertainty

  • Regan Baucke
  • Anthony Downward
  • Oscar Dowson
    • Categories Stochastic Programming Tags , , , ,

    We present a new algorithm for solving linear multistage stochastic programming problems with objective function coefficients modeled as a stochastic process. This algorithm overcomes the difficulties of existing methods which require discretization. Using an argument based on the finiteness of the set of possible cuts, we prove that the algorithm converges almost surely. Finally, we … Read more