Tight Second Stage Formulations in Two-Stage Stochastic Mixed Integer Programs
Tight Second Stage Formulations in Two-Stage Stochastic Mixed Integer Programs
复制标题
两阶段随机混合整数规划中的紧第二阶段公式
DOI：
--
复制
发表时间：
2018
影响因子：
3.1
通讯作者：
Sanjay Mehrotra
中科院分区：
文献类型：
--
作者：
M. Bansal;Kuo;Sanjay Mehrotra
研究了第二阶段随机混合整数规划问题。我们表明，在适当的条件下，第二阶段的MIP可以通过添加参数削减先验的凸性。作为特例，我们推广了米勒和沃尔西[Math. Program.，98（2003），pp. 73- 88]至TSS-MIP。此外，我们考虑第二阶段的程序，是众所周知的混合（和连续混合）集，或某些分段线性凸目标整数规划的推广。这些结果使我们能够放宽第二阶段的整数变量的完整性限制，而不影响的最优解的完整性的TSS MIP。我们还使用了四个变种的两阶段随机容量限制批量问题作为测试问题的计算实验，并提出了严格的第二阶段制定这些问题。我们的计算结果表明，增加参数不等式，先验凸的第二阶段制定的S1。
We study two-stage stochastic mixed integer programs (TSS-MIPs) with integer variables in the second stage. We show that under suitable conditions, the second stage MIPs can be convexified by adding parametric cuts a priori. As special cases, we extend the results of Miller and Wolsey [Math. Program., 98 (2003), pp. 73--88] to TSS-MIPs. Furthermore, we consider second stage programs that are generalizations of the well-known mixing (and continuous mixing) set, or certain piecewise-linear convex objective integer programs. These results allow us to relax the integrality restrictions on the second stage integer variables without effecting the integrality of the optimal solution of the TSS-MIP. We also use four variants of the two-stage stochastic capacitated lot-sizing problems as test problems for computational experiments and present tight second stage formulations for these problems. Our computational results show that adding parametric inequalities that a priori convexify the second stage formulation si...
DOI：
10.1016/j.ejor.2013.04.017
发表时间：
2013-10
期刊：
Eur. J. Oper. Res.
影响因子：
--
作者：
Christian Wolf;Achim Koberstein
通讯作者：
Christian Wolf;Achim Koberstein