Relaxations and approximations of chance constrained stochastic programs

Abstract

A chance constrained stochastic programming (CCSP) problem involves constraints with random parameters that are required to be satisfied with a prespecified probability threshold. Such constraints are used to model reliability requirements in a variety of application areas such as finance, energy, service and manufacturing. Except under very special conditions, chance constraints impart severe nonconvexities making the optimization problem extremely difficult. Moreover, in many cases, the probability distribution of the random parameters is not fully specified giving rise to additional difficulties. This thesis makes several contributions towards alleviating these two difficulties in CCSP.

In the first part of this thesis we consider CCSP problems with finitely supported probability distributions. Such problems can be reformulated as mixed integer programming (MIP) problems. We propose two new efficiently solvable Lagrangian dual problems for these problems, and show that their corresponding primal formulations lead to MIP formulations that can be stronger than traditional formulations. We next study a well-known family of cuts for these problems known as quantile cuts. We show that the closure of the infinite family of all quantile cuts has a finite description, and a recursive application of quantile closure operations recovers the convex hull of the nonconvex chance constrained set in the limit. Furthermore, we show that in the pure integer setting, the convergence is finite. Our final result in this part concerns with approximation algorithms for CCSP. We first prove that CCSP is constant factor inapproximable in general. On the other hand, for CCSP problems involving covering type constraints, we prove a bicriteria approximation result where, by relaxing the required probability threshold by a constant factor, we can provide a constant factor approximation algorithm.

In the second part of the thesis we consider distributionally robust chance constrained problems (DRCCPs) where the chance constraint is required to hold for all probability distributions of the random constraint parameters from a given ambiguity set. First, we study DRCCPs involving convex nonlinear uncertain constraints and ambiguity sets specified by convex moment constraints. We develop deterministic reformulations of such DRCCPs and identify conditions under which such reformulations are convex. Our results generalize and extend several existing results on convex reformulations of DRCCPs. Next, we apply the proposed reformulation scheme to an optimal power flow problem involving uncertainty stemming from renewable power generation. In particular, we develop a convex programming approach for a distributionally robust chance constrained optimal power flow model that ensures low probability of violating upper and lower limits of a line/bus capacity under a wide family of distributions of uncertain renewable generation. Finally, we study a conservative approximation - referred to as a Bonferroni approximation - of a joint chance constraint, i.e.~a chance constraint involving a system of multiple uncertain constraints. The Bonferroni approximation scheme uses the union bound to approximate the joint chance constraint by a system of {\em single} chance constraints, one for each original uncertain constraint and each of whose probability thresholds needs to be appropriately set. We show that such a Bonferroni approximation is exact when the uncertainties are separable across the individual constraints, i.e., each uncertain constraint involves a different set of uncertain parameters and corresponding distribution families. We show that, while in general the optimization over the Bonferroni approximation is NP-hard, there are various sufficient conditions under which it is convex and tractable.