Solving Chance-Constrained Optimization Problems with Stochastic Quadratic Inequalities

Miguel Lejeune () and François Margot ()
Additional contact information
François Margot: Tepper School of Business, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213

Operations Research, 2016, vol. 64, issue 4, 939-957

Abstract: We propose a new and systematic reformulation and algorithmic approach to solve a complex class of stochastic programming problems involving a joint chance constraint with random technology matrix and stochastic quadratic inequalities. The method is general enough to apply to nonconvex as well as nonseparable quadratic terms. We derive two new reformulations and give sufficient conditions under which the reformulated problem is equivalent. The second reformulation provides a much sparser representation of the feasible set of the chance constraint and offers tremendous computational advantages. This new reformulation method can be used for linear stochastic inequalities and will also significantly improve the solution of such joint chance-constrained problems. We provide general and easily identifiable conditions under which the base reformulations can be linearized. We show that the size of the reformulated problems, in particular, their number of binary variables and quadratic mixed-integer terms, does not grow linearly with the number of scenarios used to represent uncertainty. We propose two new nonlinear branch-and-bound algorithms for the nonconvex quadratic integer reformulations. We present detailed empirical results, comparing the various reformulations and several algorithmic ideas that improve the performance of the mixed-integer nonlinear solver Couenne for solving these problems. Guidelines on how to tune the solver and to select reformulations are presented. The test instances are epidemiology and disaster management facility location models and cover the three types of stochastic quadratic inequalities, namely, product of two decision variables that are both binary, binary and continuous, or both continuous.

Keywords: stochastic programming; mixed-integer nonlinear programming; Boolean programming; nonlinear branch-and-bound algorithm; quadratic stochastic inequality; joint probabilistic constraint; random technology matrix; epidemiology; facility location (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (11)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2016.1493 (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:64:y:2016:i:4:p:939-957

Access Statistics for this article

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