ALSO-X and ALSO-X+: Better Convex Approximations for Chance Constrained Programs

Nan Jiang () and Weijun Xie ()
Additional contact information
Nan Jiang: Department of Industrial & Systems Engineering, Virginia Tech, Blacksburg, Virginia 24061
Weijun Xie: Department of Industrial & Systems Engineering, Virginia Tech, Blacksburg, Virginia 24061

Operations Research, 2022, vol. 70, issue 6, 3581-3600

Abstract: In a chance constrained program (CCP), decision makers seek the best decision whose probability of violating the uncertainty constraints is within the prespecified risk level. As a CCP is often nonconvex and is difficult to solve to optimality, much effort has been devoted to developing convex inner approximations for a CCP, among which the conditional value-at-risk ( CVaR ) has been known to be the best for more than a decade. This paper studies and generalizes the ALSO - X , originally proposed by A hmed, L uedtke, SO ng, and X ie in 2017 , for solving a CCP. We first show that the ALSO - X resembles a bilevel optimization, where the upper-level problem is to find the best objective function value and enforce the feasibility of a CCP for a given decision from the lower-level problem, and the lower-level problem is to minimize the expectation of constraint violations subject to the upper bound of the objective function value provided by the upper-level problem. This interpretation motivates us to prove that when uncertain constraints are convex in the decision variables, ALSO - X always outperforms the CVaR approximation. We further show (i) sufficient conditions under which ALSO - X can recover an optimal solution to a CCP; (ii) an equivalent bilinear programming formulation of a CCP, inspiring us to enhance ALSO - X with a convergent alternating minimization method ( ALSO - X + ); and (iii) an extension of ALSO - X and ALSO - X + to distributionally robust chance constrained programs (DRCCPs) under the ∞ − Wasserstein ambiguity set. Our numerical study demonstrates the effectiveness of the proposed methods.

Keywords: Optimization; chance constraint; CVaR; distributionally robust; bilevel optimization (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2021.2225 (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:70:y:2022:i:6:p:3581-3600

Access Statistics for this article

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