• Login
    View Item 
    •   SMARTech Home
    • Georgia Tech Theses and Dissertations
    • Georgia Tech Theses and Dissertations
    • View Item
    •   SMARTech Home
    • Georgia Tech Theses and Dissertations
    • Georgia Tech Theses and Dissertations
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Relaxations and approximations of chance constrained stochastic programs

    Thumbnail
    View/Open
    XIE-DISSERTATION-2017.pdf (1.126Mb)
    Date
    2017-06-21
    Author
    Xie, Weijun
    Metadata
    Show full item record
    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.
    URI
    http://hdl.handle.net/1853/58678
    Collections
    • Georgia Tech Theses and Dissertations [23877]
    • School of Industrial and Systems Engineering Theses and Dissertations [1457]

    Browse

    All of SMARTechCommunities & CollectionsDatesAuthorsTitlesSubjectsTypesThis CollectionDatesAuthorsTitlesSubjectsTypes

    My SMARTech

    Login

    Statistics

    View Usage StatisticsView Google Analytics Statistics
    facebook instagram twitter youtube
    • My Account
    • Contact us
    • Directory
    • Campus Map
    • Support/Give
    • Library Accessibility
      • About SMARTech
      • SMARTech Terms of Use
    Georgia Tech Library266 4th Street NW, Atlanta, GA 30332
    404.894.4500
    • Emergency Information
    • Legal and Privacy Information
    • Human Trafficking Notice
    • Accessibility
    • Accountability
    • Accreditation
    • Employment
    © 2020 Georgia Institute of Technology