Stochastic Programming

Identifying Effective Scenarios in Distributionally Robust Stochastic Programs with Total Variation Distance

  • Hamed Rahimian
  • Güzin Bayraksan
  • Tito Homem-de-Mello
    • Categories Stochastic Programming

    Traditional stochastic programs assume that the probability distribution of uncertainty is known. However, in practice, the probability distribution oftentimes is not known or cannot be accurately approximated. One way to address such distributional ambiguity is to work with distributionally robust convex stochastic programs (DRSPs), which minimize the worst-case expected cost with respect to a set … Read more

    Two-sided linear chance constraints and extensions

  • Daniel Bienstock
  • Miles Lubin
  • Juan Pablo Vielma
    • Categories Convex Optimization, Second-Order Cone Programming, Stochastic Programming

    We examine the convexity and tractability of the two-sided linear chance constraint model under Gaussian uncertainty. We show that these constraints can be applied directly to model a larger class of nonlinear chance constraints as well as provide a reasonable approximation for a challenging class of quadratic chance constraints of direct interest for applications in … Read more

    Risk Averse Shortest Path Interdiction

  • Siqian Shen
  • Yongjia Song
    • Categories 0-1 Programming, Network Optimization, Stochastic Programming

    We consider a Stackelberg game in a network, where a leader minimizes the cost of interdicting arcs and a follower seeks the shortest distance between given origin and destination nodes under uncertain arc traveling cost. In particular, we consider a risk-averse leader, who aims to keep high probability that the follower’s traveling distance is longer … Read more

    An empirical analysis of scenario generation methods for stochastic optimization

  • Nils Löhndorf
    • Categories Stochastic Programming Tags , , , , , , ,

    This work presents an empirical analysis of popular scenario generation methods for stochastic optimization, including quasi-Monte Carlo, moment matching, and methods based on probability metrics, as well as a new method referred to as Voronoi cell sampling. Solution quality is assessed by measuring the error that arises from using scenarios to solve a multi-dimensional newsvendor … 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

    Parallel Scenario Decomposition of Risk Averse 0-1 Stochastic Programs

  • Shabbir Ahmed
  • Yan Deng
  • Siqian Shen
    • Categories 0-1 Programming, Parallel Algorithms, Stochastic Programming

    In this paper, we extend a recently proposed scenario decomposition algorithm (Ahmed (2013)) for risk-neutral 0-1 stochastic programs to the risk-averse setting. Specifically, we consider risk-averse 0-1 stochastic programs with objective functions based on coherent risk measures. Using a dual representation of a coherent risk measure, we first derive an equivalent minimax reformulation of the … Read more

    Satisficing Models under Uncertainty

  • Patrick Jaillet
  • Sanjay Dominik Jena
  • Tsan Sheng Ng
  • Melvyn Sim
    • Categories Integer Programming, Robust Optimization, Stochastic Programming Tags , , ,

    Satisficing, as an approach to decision-making under uncertainty, aims at achieving solutions that satisfy the problem’s constraints as well as possible. Mathematical optimization problems that are related to this form of decision-making include the P-model of Charnes and Cooper (1963). In this paper, we propose a general framework of satisficing decision criteria, and show a … Read more

    Scenario Set Partition Dual Bounds for Multistage Stochastic Programming: A Hierarchy of Bounds and a Partition Sampling Approach

  • Ilke Bakir
  • Natashia Boland
  • Brian Dandurand
  • Alan L. Erera
    • Categories Stochastic Programming Tags

    We consider multistage stochastic programming problems in which the random parameters have finite support, leading to optimization over a finite scenario set. We propose a hierarchy of bounds based on partitions of the scenario set into subsets of (nearly) equal cardinality. These expected partition (EP) bounds coincide with EGSO bounds provided by Sandikci et al. … Read more

    Non-asymptotic confidence bounds for the optimal value of a stochastic program

  • Vincent Guigues
  • Anatoli Juditsky
  • Arkadi Nemirovski
    • Categories Stochastic Programming

    We discuss a general approach to building non-asymptotic confidence bounds for stochastic optimization problems. Our principal contribution is the observation that a Sample Average Approximation of a problem supplies upper and lower bounds for the optimal value of the problem which are essentially better than the quality of the corresponding optimal solutions. At the same … Read more

    Constrained Optimization with Low-Rank Tensors and Applications to Parametric Problems with PDEs

  • Sebastian Garreis
  • Michael Ulbrich
    • Categories Optimization of Systems modeled by PDEs, Stochastic Programming, Systems governed by Differential Equations Optimization Tags , , , , , , ,

    Low-rank tensor methods provide efficient representations and computations for high-dimensional problems and are able to break the curse of dimensionality when dealing with systems involving multiple parameters. We present algorithms for constrained nonlinear optimization problems that use low-rank tensors and apply them to optimal control of PDEs with uncertain parameters and to parametrized variational inequalities. … Read more