On the Quantile Cut Closure of Chance-Constrained Problems
On the Quantile Cut Closure of Chance-Constrained Problems
复制标题
机会约束问题的分位数割闭合
DOI：
10.1007/978-3-319-33461-5_33
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Shabbir Ahmed
中科院分区：
文献类型：
--
作者：
Weijun Xie;Shabbir Ahmed
一个机会约束问题涉及一组场景约束，其中一个小的子集可以被违反。现有的作品通常考虑混合整数规划（MIP）制定这个问题，通过引入二进制变量，以表明哪些约束系统是满足或违反。已经开发了用于该MIP制剂的各种切割平面方法。在本文中，我们考虑了家庭的削减机会约束问题在原来的空间，而不是那些在扩展空间的MIP重构。这些切割，被称为分位数切割，可以被看作是一个投影的混合不等式的MIP重构，到原来的问题空间的众所周知的家庭。我们展示了以下结果关于分位数切割：（i）封闭的所有分位数切割是一个多面体集;（ii）分离的分位数切割一般是NP-困难的;（iii）连续应用分位数切割关闭实现凸船体的机会约束问题的限制;和（iv）在纯整数设置这种收敛是有限的。
A chance constrained problem involves a set of scenario constraints from which a small subset can be violated. Existing works typically consider a mixed integer programming (MIP) formulation of this problem by introducing binary variables to indicate which constraint systems are to be satisfied or violated. A variety of cutting plane approaches for this MIP formulation have been developed. In this paper we consider a family of cuts for chance constrained problems in the original space rather than those in the extended space of the MIP reformulation. These cuts, known as quantile cuts, can be viewed as a projection of the well known family of mixing inequalities for the MIP reformulation, onto the original problem space. We show the following results regarding quantile cuts: (i) the closure of all quantile cuts is a polyhedral set; (ii) separation of quantile cuts is in general NP-hard; (iii) successive application of quantile cut closures achieves the convex hull of the chance constrained problem in the limit; and (iv) in the pure integer setting this convergence is finite.