stochastic programming

Communication-Efficient Algorithms for Decentralized and Stochastic Optimization

  • Guanghui Lan
  • Soomin Lee
  • Yi Zhou
    • Categories Convex and Nonsmooth Optimization, Stochastic Programming Tags , , , , , ,

    We present a new class of decentralized first-order methods for nonsmooth and stochastic optimization problems defined over multiagent networks. Considering that communication is a major bottleneck in decentralized optimization, our main goal in this paper is to develop algorithmic frameworks which can significantly reduce the number of inter-node communications. We first propose a decentralized primal-dual … Read more

    Second-order cone programming formulation for two player zero-sum game with chance constraints

  • Abdel Lisser
  • Vikas Vikram Singh
    • Categories Game Theory, Stochastic Programming Tags , , , ,

    We consider a two player finite strategic zero-sum game where each player has stochastic linear constraints. We formulate the stochastic constraints of each player as chance constraints. We show the existence of a saddle point equilibrium if the row vectors of the random matrices, defining the stochastic constraints of each player, are elliptically symmetric distributed … Read more

    Combining Penalty-based and Gauss-Seidel Methods for solving Stochastic Mixed-Integer Problems

  • Eberhard Andrew
  • Brian Dandurand
  • Fabricio Oliveira
  • Jeffrey Christiansen
    • Categories Stochastic Programming Tags , , , ,

    In this paper, we propose a novel decomposition approach for mixed-integer stochastic programming (SMIP) problems that is inspired by the combination of penalty-based Lagrangian and block Gauss-Seidel methods (PBGS). In this sense, PBGS is developed such that the inherent decomposable structure that SMIPs present can be exploited in a computationally efficient manner. The performance of … Read more

    Decision Rule Bounds for Two-Stage Stochastic Bilevel Programs

  • Daniel Kuhn
  • Ihsan Yanıkoğlu
    • Categories Robust Optimization, Stochastic Programming Tags , ,

    We study stochastic bilevel programs where the leader chooses a binary here-and-now decision and the follower responds with a continuous wait-and-see-decision. Using modern decision rule approximations, we construct lower bounds on an optimistic version and upper bounds on a pessimistic version of the leader’s problem. Both bounding problems are equivalent to explicit mixed-integer linear programs … Read more

    Distributionally Robust Optimization with Infinitely Constrained Ambiguity Sets

  • Melvyn Sim
  • Huan Xu
  • Zhi Chen
    • Categories Robust Optimization Tags ,

    We consider a distributionally robust optimization problem where the ambiguity set of probability distributions is characterized by a tractable conic representable support set and expectation constraints. Specifically, we propose and motivate a new class of infinitely constrained ambiguity sets in which the number of expectation constraints could potentially be infinite. We show how the infinitely … Read more

    Decomposability and time consistency of risk averse multistage programs

  • Alexander Shapiro
  • Kerem Ugurlu
    • Categories Stochastic Programming Tags , ,

    Two approaches to time consistency of risk averse multistage stochastic problems were dis- cussed in the recent literature. In one approach certain properties of the corresponding risk measure are postulated which imply its decomposability. The other approach deals directly with conditional optimality of solutions of the considered problem. The aim of this paper is to … Read more

    Pricing wind: a revenue adequate, cost recovering uniform auction for electricity markets with intermittent generation

  • Endre Bjorndal
  • Mette Bjorndal
  • Geoff Pritchard
  • Golbon Zakeri
    • Categories Applications - OR and Management Sciences, Stochastic Programming Tags , ,

    With greater penetration of renewable generation, the uncertainty faced in electricity markets has increased substantially. Conventionally, generators are assigned a pre-dispatch quantity in advance of real time, based on estimates of uncertain quantities. Expensive real time adjustments then need to be made to ensure demand is met, as uncertainty takes on a realization. We propose … Read more

    Distributionally Robust Optimization with Principal Component Analysis

  • Richard Chen
  • Habib Najm
  • Jean-Paul Watson
  • Jianqiang Cheng
  • Ali Pinar
  • Cosmin Safta
    • Categories Robust Optimization, Stochastic Programming Tags , , ,

    Distributionally robust optimization (DRO) is widely used, because it offers a way to overcome the conservativeness of robust optimization without requiring the specificity of stochastic optimization. On the computational side, many practical DRO instances can be equivalently (or approximately) formulated as semidefinite programming (SDP) problems via conic duality of the moment problem. However, despite being … Read more

    Exact Algorithms for the Chance-Constrained Vehicle Routing Problem

  • Thai Dinh
  • Ricardo Fukasawa
  • James R. Luedtke
    • Categories 0-1 Programming, Stochastic Programming, Transportation Tags , ,

    We study the chance-constrained vehicle routing problem (CCVRP), a version of the vehicle routing problem (VRP) with stochastic demands, where a limit is imposed on the probability that each vehicle’s capacity is exceeded. A distinguishing feature of our proposed methodologies is that they allow correlation between random demands, whereas nearly all existing exact methods for … Read more

    A stochastic program with tractable time series and affine decision rules for the reservoir management problem

  • Erick Delage
  • Charles Gauvin
  • Michel Gendreau
    • Categories Applications - OR and Management Sciences, Robust Optimization, Stochastic Programming Tags , , , , ,

    This paper proposes a multi-stage stochastic programming formulation for the reservoir management problem. Our problem specifically consists in minimizing the risk of floods over a fixed time horizon for a multi-dimensional hydro-electrical complex. We consider well-studied linear time series model and enhance the approach to consider heteroscedasticity. Using these stochastic processes under very general distributional … Read more