Scenario-based cuts for structured two-stage stochastic and distributionally robust p-order conic mixed integer programs
Scenario-based cuts for structured two-stage stochastic and distributionally robust p-order conic mixed integer programs
复制标题
DOI：
10.1007/s10898-020-00986-w
复制
发表时间：
2021-01
影响因子：
1.8
通讯作者：
M. Bansal;Yingqiu Zhang
中科院分区：
文献类型：
--
作者：
M. Bansal;Yingqiu Zhang
本文利用Atamtürk和Narayanan（Math Prog 122：1-20，2008）的圆锥混合整数舍入（CMIR）割生成方法，导出了确定性多约束多整数变量多面体圆锥混合整数集的（部分）凸船体，从而将他们的结果推广到单约束单整数变量多面体圆锥混合整数集.然后，我们引入两阶段的随机p阶圆锥混合整数规划（表示为TSS-CMIP），其中第二阶段的问题有和的范数的目标函数沿着与整数变量。首先，我们提出了充分的条件下，在广泛制定的TSS-CMIP的增加的基于非线性切割是足以放宽第二阶段的整数变量的完整性限制，而不影响的完整性的最优解的TSS-CMIP。在第二阶段，我们利用TSS-CMIP和其分布鲁棒的推广与结构化CMIP基于CNOMO的CMIR削减，并证明这些削减提供圆锥/线性规划等价或近似的第二阶段CMIP。我们还进行了广泛的计算实验，通过解决随机和分布鲁棒的能力约束的设施选址问题和随机生成的结构TSS-CMIP与多面体CMIP和二阶CMIP在第二阶段，即和，分别。我们注意到，在加上以比索为基础的削减之后，解决这些问题所需的总时间大大减少。
In this paper, we derive (partial) convex hull for deterministic multi-constraint polyhedral conic mixed integer sets with multiple integer variables using conic mixed integer rounding (CMIR) cut-generation procedure of Atamtürk and Narayanan (Math Prog 122:1–20, 2008), thereby extending their result for a simple polyhedral conic mixed integer set with single constraint and one integer variable. We then introduce two-stage stochasticp-order conic mixed integer programs (denoted by TSS-CMIPs) in which the second stage problems have sum of-norms in the objective function along with integer variables. First, we present sufficient conditions under which the addition of scenario-based nonlinear cuts in the extensive formulation of TSS-CMIPs is sufficient to relax the integrality restrictions on the second stage integer variables without impacting the integrality of the optimal solution of the TSS-CMIP. We utilize scenario-based CMIR cuts for TSS-CMIPs and their distributionally robust generalizations with structured CMIPs in the second stage, and prove that these cuts provide conic/linear programming equivalent or approximation for the second stage CMIPs. We also perform extensive computational experiments by solving stochastic and distributionally robust capacitated facility location problem and randomly generated structured TSS-CMIPs with polyhedral CMIPs and second-order CMIPs in the second stage, i.e.and, respectively. We observe that there is a significant reduction in the total time taken to solve these problems after adding the scenario-based cuts.