两阶段随机混合整数规划的求解方法与技术

### 两阶段随机混合整数规划的求解方法与技术 #### 1. 两阶段随机混合整数规划基础 在两阶段随机混合整数规划中，我们会遇到一系列的约束条件和目标函数。首先有如下约束条件： \[ \begin{cases} \sum_{q\in Q_s}\frac{1}{2}\eta + \overline{\lambda}_{qs}T_sx \geq \overline{\lambda}_{qs}r_s + \overline{\psi}_{qls}z_{qls} - \overline{\psi}_{qus}z_{qus}\\ Ax \geq b \end{cases} \] 这里，\(\overline{\eta}\) 是第二阶段值函数的当前估计下界，可能是从之前的迭代中得到的。设 \((\overline{\sigma}_s, \overline{\upsilon}_s, \overline{\delta}_s)\) 是以下线性规划的最优极点解： - **目标函数**：最小化 \(\sigma_s\overline{x} + \upsilon_s\overline{\eta} - \delta_s\) - **约束条件**： - \(\sigma_s - \tau_qA - \theta_q\overline{\lambda}_{qs}T_s \geq 0, \forall q \in Q_s\) - \(\upsilon_s - \theta_q \geq 0, \forall q \in Q_s\) - \(\tau_qb + \theta_q(\overline{\lambda}_{qs}r_s + \overline{\psi}_{qls}z_{qls} - \overline{\psi}_{qus}z_{qus}) - \delta_s \geq 0, \forall q \in Q_s\) - \(\sum_{q\in Q_s}\theta_q = 1\) - \(\theta, \tau \geq 0\)，\(\sigma, \delta, \upsilon\) 无限制 由于上述约束中的条件，我们可知 \(\overline{\upsilon}_s > 0\)。此时，能得到一个关于第二阶段值函数下界的析取割平面，形式为 \(\eta_s \geq \overline{\gamma}_s - \overline{\alpha}_sx\)，其中 \(\overline{\alpha}_s = \overline{\sigma}_s / \overline{\upsilon}_s\)，\(\overline{\gamma}_s = \overline{\delta}_s / \overline{\upsilon}_s\)。 #### 2. 纯连续和混合 0 - 1 第一阶段问题 依据割平面博弈的概念，析取和 RLT 割平面生成过程能有限地求解第二阶段子问题。像 Sen 和 Higle 的 D2 算法以及 Sherali 和 Fraticelli 的改进 Benders 分解算法，由于第一阶段可行解数量有限以及求解子问题的割平面生成过程有限，能保证有限收敛。 然而，当第一阶段包含连续变量时，可行的第一阶段解 \(\overline{x}\) 可能不满足其边界约束的面性质，上述算法就无法保证收敛。为了保留第一阶段解的面性质，Ntaimo 和 Sen 以及 Sherali 和 Zhu 提出通过在有界第一阶段变量的投影空间中进行分区过程来构建分支定界（B&B）树，从而最终实现面性质。 ##### 2.1 D2 - CBAC 算法 对于仅包含纯连续第一阶段变量的问题，Ntaimo 和 Sen 提出了有限收敛的基于 D2 的分支 - 割（D2 - CBAC）算法。该算法的步骤如下： 1. 在第一阶段可行区域上构建 B&B 树。 2. 在每个节点应用 D2 算法。 3. 选择某个场景 \(s\) 和迭代 \(k\)，使得 \(\overline{\gamma}_s - \overline{\alpha}_sx = \min\{\overline{\lambda}_0r_s - \overline{\lambda}_0T_sx, \overline{\lambda}_1r_s + \varsigma_1 - \overline{\lambda}_1T_sx\}\) 这个等式被最大程度地违反。 4. 根据上述等式产生的析取进行分区，在一个子节点上强制 \(\overline{\lambda}_0r_s - \overline{\lambda}_0T_sx \geq \overline{\lambda}_1r_s + \varsigma_1 - \overline{\lambda}_1T_sx\)，在另一个子节点上强制 \(\overline{\lambda}_0r_s - \overline{\lambda}_0T_sx \leq \overline{\lambda}_1r_s + \varsigma_1 - \overline{\lambda}_1T_sx\)。 5. 相应地更新父节点的凸化割平面，在两个子节点分别更新为 \(\overline{\beta}y \geq \overline{\lambda}_k^0r_k^s - \overline{\lambda}_k^0T_k^sx\) 和 \(\overline{\beta}y \geq \overline{\lambda}_k^1r_s + \varsigma_k^1 - \overline{\lambda}_k^1T_k^sx\)。 由于第二阶段的析取变量数量有限，在嵌入式 D2 算法的某些迭代中，能构建的约束右边项数量有限，所以第一阶段可行区域的分区数量有限，从而保证了 D2 - CBAC 算法的有限收敛。 ##### 2.2 DBAB 算法 当第一阶段同时包含连续和二进制变量时，Sherali 和 Zhu 提出了基于分解的 B&B（DBAB）算法，该算法能保证收敛到最优解。算法假设在 \(x\) 的某个边界超矩形上具有相对完全的补偿。具体步骤如下： 1. 在有界第一阶段变量的投影空间上定义 B&B 树。 2. 通过应用从 Sherali 和 Fraticelli 扩展而来的改进 Benders 方法，在原始 \(x\) 边界超矩形的细分上计算节点问题的下界。 3. 根据第二阶段约束和当前 \(x\) 的边界约束，在 \((x, y_s)\) 空间中基于部分凸包表示导出 Benders 子问题。 4. 在分支定界过程中，每次分区步骤选择下界最小的节点进行分支。 5. 在分区步骤中，对第一阶段的连续和二进制变量区别处理： - 选择当前值最接近其边界中间的变量 \(x_p\) 作为分区变量。 - 如果 \(p \in I_b\)，则在两个子节点分别将 \(x_p\) 固定为 0 和 1。 - 否则，\(x_p\) 是连续变量，将其当前值 \(\overline{x}_p\)（或当前边界区间的中点）分别作为两个子节点的下界和上界。 这样，沿着 B&B 树的任何无限分支，存在某个连续变量 \(x_p\) 的边界区间被无限次分区，且其极限值 \(\overline{x}_p\) 与某个边界重合，最终 \(\overline{x}\) 成为极限边界超矩形的顶点，为原始两阶段随机规划提供上界解。结合节点选择规则，分区过程保证了算法收敛到最优解。 在直接实现改进 Benders 方法时，当 \(\overline{x}\) 不是其边界的极值点时，在 \((x, y)\) 空间的部分凸包表示上定义的 Benders 子问题得到的解 \(\overline{y}\) 可能不满足其二进制限制。判断 Benders 子问题是否已由这样的分数解 \(\overline{y}\) 解决的方法如下：如果 \(\overline{y}_j \in \{0, 1\}, \forall j \in J_b\)，或者 \((\overline{x}, \overline{y})\) 可以表示为当前定义 Benders 子问题的部分凸包的某些极点的凸组合，且这些极点的 \(y_j\) 变量对于所有 \(j \in J_b\) 都是二进制的，则 \(\overline{y}\) 解决了 Benders 子问题。 此外，为任何给定的子超矩形生成的 RLT 割平面可以通过在同一节点的后续 Benders 迭代中更新 \(x\) 值来重复使用，并且可以由子节点的子问题继承。同样，为给定子超矩形导出的 Benders 割平面也可以由其子节点求解的下界主程序继承。 #### 3. 析取割平面和 RLT 割平面的联系 这里主要探讨在固定补偿的随机规划中，由问题 (12.16) 和 (12.20) 生成的析取割平面与由问题 (12.24) 生成的 RLT 割平面之间的联系，以连续第一阶段变量的情况为例，离散情况分析类似。 设 \(x\) 是连续的，且在 B&B 过程的某个节点上受 \(l \leq x \leq u\) 约束。将约束 \(T_sx + \tilde{W}\tilde{y} + W^qy^q \geq r_s\) 和 \(l \leq x \leq u\) 分别乘以 \(y^q\) 和 \((1 - y^q)\)，并使用 (12.22) 对结果中的非线性项进行线性化，得到更高维的系统： - \(T_sz_x + \tilde{W}z_y \geq (r_s - W^q)y^q \leftarrow \varphi_0\) - \(-T_sz_x - \tilde{W}z_y \geq r_s - T_sx - \tilde{W}\tilde{y} - r_sy^q \leftarrow \varphi_1\) - \(z_x \geq ly^q \leftarrow \varphi_{xl0}\) - \(-z_x \geq -uy^q \leftarrow \varphi_{xu0}\) - \(-z_x \geq -ly^q + l - x \leftarrow \varphi_{xl1}\) - \(z_x \geq uy^q - u + x \leftarrow \varphi_{xu1}\) 对应的割平面生成问题形式如下： - **目标函数**：最小化 \(\tilde{\beta}_s\overline{\tilde{y}} + \beta_{qs}\overline{y}^q + \alpha_s\overline{x} - \gamma_s\) - **约束条件**： - \((\varphi_0 - \varphi_1)T_s + \varphi_{xl0} - \varphi_{xu0} - \varphi_{xl1} + \varphi_{xu1} = 0\) - \((\varphi_0 - \varphi_1)\tilde{W} = 0\)