chance constraints

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

    On the Safety First portfolio selection

  • Serhiy Boyko
  • Vladimir I. Norkin
    • Categories Finance and Economics, Stochastic Programming Tags , , , ,

    A.D.Roy’s (1952) safety first (SF) approach to a financial portfolio selection is improved. Safety first means minimization of probability of poor returns. Improvement concerns a better estimation of the poor return probabilities by means of shortfall risk functions. Optimal SF-portfolio is sought similar to Roy’s geometric method but with a different efficient frontier. In case … Read more