2019/10/03 by Fatma Kılınç-Karzan, Si̇mge Küçükyavuz, Kılınç-Karzan, Fatma +3 · 1 citation
Decision Sciences · #90C11 #90C15 #FOS: Mathematics #Optimization and Control (math.OC) #Risk and Portfolio Optimization
paper · pdf · doi:10.48550/arxiv.1910.01353
openalex publication_date 2019/10/03 · openalex created_date 2022/07/28 · openalex updated_date 2026/07/28
A particularly important substructure in modeling joint linear\nchance-constrained programs with random right-hand sides and finite sample\nspace is the intersection of mixing sets with common binary variables (and\npossibly a knapsack constraint). In this paper, we first revisit basic mixing\nsets by establishing a strong and previously unrecognized connection to\nsubmodularity. In particular, we show that mixing inequalities with binary\nvariables are nothing but the polymatroid inequalities associated with a\nspecific submodular function. This submodularity viewpoint enables us to unify\nand extend existing results on valid inequalities and convex hulls of the\nintersection of multiple mixing sets with common binary variables. Then, we\nstudy such intersections under an additional linking constraint lower bounding\na linear function of the continuous variables. This is motivated from the\ndesire to exploit the information encoded in the knapsack constraint arising in\njoint linear CCPs via the quantile cuts. We propose a new class of valid\ninequalities and characterize when this new class along with the mixing\ninequalities are sufficient to describe the convex hull.\n