TY - JOUR

T1 - On intersection of two mixing sets with applications to joint chance-constrained programs

AU - Liu, Xiao

AU - Kılınç-Karzan, Fatma

AU - Küçükyavuz, Simge

N1 - Funding Information:
We thank the two anonymous reviewers for their comments that improved the presentation. Simge K???kyavuz and Xiao Liu are supported, in part, by National Science Foundation Grants 1732364 and 1733001. Fatma K?l?n?-Karzan is supported in part by NSF grant CMMI 1454548.
Funding Information:
Acknowledgements We thank the two anonymous reviewers for their comments that improved the presentation. Simge Küçükyavuz and Xiao Liu are supported, in part, by National Science Foundation Grants 1732364 and 1733001. Fatma Kılınç-Karzan is supported in part by NSF grant CMMI 1454548.

PY - 2019/5/1

Y1 - 2019/5/1

N2 - We study the polyhedral structure of a generalization of a mixing set described by the intersection of two mixing sets with two shared continuous variables, where one continuous variable has a positive coefficient in one mixing set, and a negative coefficient in the other. Our developments are motivated from a key substructure of linear joint chance-constrained programs (CCPs) with random right hand sides from a finite probability space. The CCPs of interest immediately admit a mixed-integer programming reformulation. Nevertheless, such standard reformulations are difficult to solve at large-scale due to the weakness of their linear programming relaxations. In this paper, we initiate a systemic polyhedral study of such joint CCPs by explicitly analyzing the system obtained from simultaneously considering two linear constraints inside the chance constraint. We carry out our study on this particular intersection of two mixing sets under a nonnegativity assumption on data. Mixing inequalities are immediately applicable to our set, yet they are not sufficient. Therefore, we propose a new class of valid inequalities in addition to the mixing inequalities, and establish conditions under which these inequalities are facet defining. Moreover, under certain additional assumptions, we prove that these new valid inequalities along with the classical mixing inequalities are sufficient in terms of providing the closed convex hull description of our set. We also show that linear optimization over our set is polynomial-time, and we independently give a (high-order) polynomial-time separation algorithm for the new inequalities. We complement our theoretical results with a computational study on the strength of the proposed inequalities. Our preliminary computational experiments with a fast heuristic separation approach demonstrate that our proposed inequalities are practically effective as well.

AB - We study the polyhedral structure of a generalization of a mixing set described by the intersection of two mixing sets with two shared continuous variables, where one continuous variable has a positive coefficient in one mixing set, and a negative coefficient in the other. Our developments are motivated from a key substructure of linear joint chance-constrained programs (CCPs) with random right hand sides from a finite probability space. The CCPs of interest immediately admit a mixed-integer programming reformulation. Nevertheless, such standard reformulations are difficult to solve at large-scale due to the weakness of their linear programming relaxations. In this paper, we initiate a systemic polyhedral study of such joint CCPs by explicitly analyzing the system obtained from simultaneously considering two linear constraints inside the chance constraint. We carry out our study on this particular intersection of two mixing sets under a nonnegativity assumption on data. Mixing inequalities are immediately applicable to our set, yet they are not sufficient. Therefore, we propose a new class of valid inequalities in addition to the mixing inequalities, and establish conditions under which these inequalities are facet defining. Moreover, under certain additional assumptions, we prove that these new valid inequalities along with the classical mixing inequalities are sufficient in terms of providing the closed convex hull description of our set. We also show that linear optimization over our set is polynomial-time, and we independently give a (high-order) polynomial-time separation algorithm for the new inequalities. We complement our theoretical results with a computational study on the strength of the proposed inequalities. Our preliminary computational experiments with a fast heuristic separation approach demonstrate that our proposed inequalities are practically effective as well.

KW - Branch-and-cut

KW - Convex hull

KW - Mixing inequalities

KW - Separation

KW - Two-sided/joint chance-constraints

UR - http://www.scopus.com/inward/record.url?scp=85040779913&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85040779913&partnerID=8YFLogxK

U2 - 10.1007/s10107-018-1231-2

DO - 10.1007/s10107-018-1231-2

M3 - Article

AN - SCOPUS:85040779913

VL - 175

SP - 29

EP - 68

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

IS - 1-2

ER -