Bicriteria Approximation of Chance-Constrained Covering Problems

Weijun Xie () and Shabbir Ahmed ()
Additional contact information
Weijun Xie: Department of Industrial and Systems Engineering, Virginia Tech, Blacksburg, Virginia 2406
Shabbir Ahmed: School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332

Operations Research, 2020, vol. 68, issue 2, 516-533

Abstract: A chance-constrained optimization problem involves constraints with random data that can be violated with probability bounded from above by a prespecified small risk parameter. 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-constrained problems are extremely difficult. There has been a great deal of elegant work on developing tractable approximations of chance constraints. Unfortunately, none of these approaches comes with a constant factor approximation guarantee. We show that such a guarantee is impossible by proving an inapproximability result. By contrast, for a large class of chance-constrained covering problems, we propose a bicriteria approximation scheme. Our scheme finds a solution whose violation probability may be larger than but is within a constant factor of the specified risk parameter and whose objective value is within a constant factor of the true optimal value. Key to our developments is the construction of a tractable convex relaxation of a chance-constrained problem and an appropriate scaling of a solution to this relaxation. We extend our approximation results to the setting in which the underlying distribution of the constraint data is not known. That is, we consider distributionally robust chance-constrained covering problems with convex moment and Wasserstein ambiguity sets and provide bicriteria approximation results.

Keywords: chance-constrained problem; approximation algorithm; distributionally robust optimization; convex relaxation (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://doi.org/10.1287/opre.2019.1866 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:68:y:2020:i:2:p:516-533

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().