Optimization Online


Risk Optimization in Probabilistic Programs with Single or Multiple Chance Constraints

Siqian Shen (siqian***at***umich.edu)

Abstract: Problems of probabilistic programming, also referred to as chance-constrained programming (CCP), evaluate value-at-risks of uncertain events, and permit certain tolerances for such risks. In this paper, we optimize risk tolerances as decision variables in CCP models, which by assumption only contain random discretely distributed right-hand sides. The paper first considers a bilevel interdiction problem, in which an inner problem contains one single-row chance constraint, while an outer problem decides the risk tolerance associated with the constraint, to maximize the minimum objective computed by the inner problem. For optimizing the risk tolerance, we show that only finite possible values matter to the inner CCP objective, and interpret the risk variable as Special Ordered Set of Type 1 (SOS1) binary variables. We then transform the bilevel program into a deterministic integer programming formulation, whose size depends on the set cardinality of all possible realizations of right-hand sides. We also extend our investigation to CCP models with multiple single-row chance constraints, each of which has an associated risk tolerance variable. The goal is to seek an optimal combination of risks to minimize the overall objective value in the resulting CCP. This paper reformulates the problem as an integer program in multiple SOS1 binary variables, and employs a decomposition strategy for solving the reformulation. We demonstrate the two model variants by respectively solving a stochastic minimum-cost flow problem and a multicommodity flow capacity expansion problem on a set of randomly generated graph instances.

Keywords: Chance-constrained programming, Special Ordered Set of Type 1 (SOS1), mixed-integer programming, Benders decomposition, risk optimization

Category 1: Stochastic Programming

Category 2: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 3: Integer Programming (Cutting Plane Approaches )

Citation: Department of Industrial and Operations Engineering, University of Michigan

Download: [PDF]

Entry Submitted: 06/10/2012
Entry Accepted: 06/11/2012
Entry Last Modified: 06/25/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society