chance constraints

REDUCTION OF TWO-STAGE PROBABILISTIC OPTIMIZATION PROBLEMS WITH DISCRETE DISTRIBUTION OF RANDOM DATA TO MIXED INTEGER PROGRAMMING PROBLEMS

  • Andrey Kibzun
  • Vladimir I. Norkin
  • Andrey Naumov
    • Categories (Mixed) Integer Nonlinear Programming, Nonsmooth Optimization, Stochastic Programming Tags , , , , ,

    We consider models of two-stage stochastic programming with a quantile second stage criterion and optimization models with a chance constraint on the second stage objective function values. Such models allow to formalize requirements to reliability and safety of the system under consideration, and to optimize the system in extreme conditions. We suggest a method of … Read more

    On reducing a quantile optimization problem with discrete distribution to a mixed integer programming problem

  • Andrey Kibzun
  • Vladimir I. Norkin
  • Andrey Naumov
    • Categories (Mixed) Integer Nonlinear Programming, Finance and Economics, Stochastic Programming Tags , , , , ,

    We suggest a method for equivalent transformation of a quantile optimization problem with discrete distribution of random parameters to mixed integer programming problems. The number of additional integer (in fact boolean) variables in the equivalent problems equals to the number of possible scenarios for random data. The obtained mixed integer problems are solved by standard … Read more

    Chance-constrained binary packing problems

  • Simge Küçükyavuz
  • James R. Luedtke
  • Yongjia Song
    • Categories Integer Programming, Stochastic Programming Tags ,

    We consider a class of packing problems with uncertain data, which we refer to as the chance-constrained binary packing problem. In this problem, a subset of items is selected that maximizes the total profit so that a generic packing constraint is satisfied with high probability. Interesting special cases of our problem include chance-constrained knapsack and … Read more

    Branch-and-cut Approaches for Chance-constrained Formulations of Reliable Network Design Problems

  • James R. Luedtke
  • Yongjia Song
    • Categories Branch and Cut Algorithms, Stochastic Programming Tags , ,

    We study solution approaches for the design of reliably connected networks. Speci fically, given a network with arcs that may fail at random, the goal is to select a minimum cost subset of arcs such the probability that a connectivity requirement is satis ed is at least 1-\epsilon, where \epsilon is a risk tolerance. We consider two … Read more

    Convex relaxations of chance constrained optimization problems

  • Shabbir Ahmed
    • Categories Stochastic Programming Tags ,

    In this paper we develop convex relaxations of chance constrained optimization problems in order to obtain lower bounds on the optimal value. Unlike existing statistical lower bounding techniques, our approach is designed to provide deterministic lower bounds. We show that a version of the proposed scheme leads to a tractable convex relaxation when the chance … Read more

    A Branch-and-Cut Decomposition Algorithm for Solving Chance-Constrained Mathematical Programs with Finite Support

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

    We present a new approach for exactly solving chance-constrained mathematical programs having discrete distributions with nite support and random polyhedral constraints. Such problems have been notoriously difficult to solve due to nonconvexity of the feasible region, and most available methods are only able to nd provably good solutions in certain very special cases. Our approach … Read more

    Concepts and Applications of Stochastically Weighted Stochastic Dominance

  • Tito Homem-de-Mello
  • Jian Hu
  • Sanjay Mehrotra
    • Categories Applications - OR and Management Sciences, Multi-Criteria Optimization, Stochastic Programming Tags , , , ,

    Stochastic dominance theory provides tools to compare random entities. When comparing random vectors (say X and Y ), the problem can be viewed as one of multi-criterion decision making under uncertainty. One approach is to compare weighted sums of the components of these random vectors using univariate dominance. In this paper we propose new concepts … Read more

    A Chance-Constrained Model & Cutting Planes for Fixed Broadband Wireless Networks

  • Grit Claßen
  • Arie M.C.A. Koster
  • David Coudert
  • Napoleao Nepomuceno
    • Categories Cutting Plane Approaches, Robust Optimization, Telecommunications Tags , , ,

    In this paper, we propose a chance-constrained mathematical program for fixed broadband wireless networks under unreliable channel conditions. The model is reformulated as integer linear program and valid inequalities are derived for the corresponding polytope. Computational results show that by an exact separation approach the optimality gap is closed by 42 % on average. ArticleDownload … Read more

    Chance-Constrained Linear Matrix Inequalities with Dependent Perturbations: A Safe Tractable Approximation Approach

  • Sin-Shuen Cheung
  • Anthony Man-Cho So
  • Kuncheng Wang
    • Categories Robust Optimization Tags , ,

    The wide applicability of chance-constrained programming, together with advances in convex optimization and probability theory, has created a surge of interest in finding efficient methods for processing chance constraints in recent years. One of the successes is the development of so-called safe tractable approximations of chance-constrained programs, where a chance constraint is replaced by a … Read more

    Distributionally Robust Joint Chance Constraints with Second-Order Moment Information

  • Daniel Kuhn
  • Berc Rustem
  • Steve Zymler
    • Categories Robust Optimization Tags , ,

    We develop tractable semidefinite programming (SDP) based approximations for distributionally robust individual and joint chance constraints, assuming that only the first- and second-order moments as well as the support of the uncertain parameters are given. It is known that robust chance constraints can be conservatively approximated by Worst-Case Conditional Value-at-Risk (CVaR) constraints. We first prove … Read more