Joint chance-constrained programs and the intersection of mixing sets through a submodularity lens

• 成果类型: Article
• 署名作者: Kilinc-Karzan, Fatma; Kucukyavuz, Simge; Lee, Dabeen
• 署名单位: Carnegie Mellon University; Northwestern University; Institute for Basic Science - Korea (IBS)
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-021-01688-1
• 发表日期: 2022
• 页码: 283-326
• 关键词: Optimization; minimization; formulations

摘要

A particularly important substructure in modeling joint linear chance-constrained programs with random right-hand sides and finite sample space is the intersection of mixing sets with common binary variables (and possibly a knapsack constraint). In this paper, we first revisit basic mixing sets by establishing a strong and previously unrecognized connection to submodularity. In particular, we show that mixing inequalities with binary variables are nothing but the polymatroid inequalities associated with a specific submodular function. This submodularity viewpoint enables us to unify and extend existing results on valid inequalities and convex hulls of the intersection of multiple mixing sets with common binary variables. Then, we study such intersections under an additional linking constraint lower bounding a linear function of the continuous variables. This is motivated from the desire to exploit the information encoded in the knapsack constraint arising in joint linear CCPs via the quantile cuts. We propose a new class of valid inequalities and characterize when this new class along with the mixing inequalities are sufficient to describe the convex hull.