Relaxations for probabilistically constrained programs with discrete random variables

Abstract

We consider mathematical programs with probabilistic constraints in which the random variables are discrete. In general, the feasible region associated with such problems is nonconvex. We use methods of disjunctive programming to approximate the convex hull of the feasible region. For a particular disjunctive set implied by the probabilistic constraint, we characterize the set of all valid inequalities as well as the facets of the convex hull of the given disjunctive set. These may be used within relaxation methods, especially for combinatorial optimization problems.