论文题目：Improving the Integer L-Shaped Method
第一作者：Gustavo Angulo, an associate professor at the Department of Industrial and Systems Engineering of Pontificia Universidad Católica de Chile.研究聚集混合整数规划和随机规划。
E-mail：gangulo@ing.puc.cl
通讯作者：Santanu S. Dey 佐治亚理工学院工业与系统工程学院教授，研究混合整数线性规划、混合整数非线性规划等，担任《 Computational Optimization and Applications》期刊的编委，《Mathematics of Operations Research》, 《Mathematical Programming A》, 《SIAM Journal on Optimization》副主编，曾任《INFORMS Journal on Computing》副主编。
E-mail：santanu.dey@isye.gatech.edu
两阶段随机规划：交替与扩展切割的整数 L 型法
论文摘要
这篇论文关注两阶段随机混合整数规划中整数 L 型法的性能瓶颈。传统的整数 L 型法通过松弛二次约束并不断加入子梯度切割和整数最优性切割，逼近二阶段成本函数 的上图像。然而二阶段问题涉及整数变量时， 可能非凸甚至不连续，导致算法需要大量求解昂贵的混合整数子问题。本研究提出两种改进策略：一是交替切割策略，先用连续松弛代替精确的二阶段评估，用子梯度切割快速剔除无效解，从而减少昂贵的混合整数求解；二是基于切割生成线性规划（CGLP） 的新的整数最优性切割，通过利用已知解的信息构造更紧的上图像凸包。这两种策略相互补充，既降低了计算负担，又改善了 的逼近质量。数值实验显示，在随机旅行商和随机装箱等实例上，改进后的算法相较标准方法能取得一个数量级的加速。
一、研究背景与问题定义
1.1 两阶段随机混合整数规划
模型形式。论文考虑如下混合整数规划
其中 是对随机二阶段问题的期望成本。若 满足所有约束，则为可行解。第一阶段变量 为二进制向量，第二阶段随机问题求解
通常需要混合整数编程。
复杂性来源。当随机场景数目巨大时，直接求解（IP）代价昂贵。Benders 分解和 L 型法等分解技术在二阶段线性情况下有效。但当二阶段含整数变量时， 非凸并可能不连续；传统 L 型法需要针对每个整数 计算精确的 ，成本极高。
1.2 整数 L 型法概述
标准整数 L 型法将问题（IP）等价转化为主问题
其中 是在已知点 上用最优性切割逼近 的仿射下界。算法流程为：
对二阶段期望成本 给出一个下界 。 先求解问题（IP）的线性松弛，用子梯度切割得到初始主问题。 强制 为二进制变量后，用分支–割算法解主问题。当发现候选整数解 时，如果 ，则通过整数最优性切割将该解排除；否则更新最优解。 过程在搜索树各节点重复，直到找到满足 的最优解。
虽然此方法可解决大规模随机整数问题，但其瓶颈在于每次发现候选解都需计算精确的 ，即需求解混合整数子问题，并且传统整数最优性切割的形式
依赖于枚举 的所有 0/1 位置，切割质量有限。
二、交替切割策略：降低评估成本
2.1 思路与关键步骤
考虑一次搜索树节点中出现的候选解 。标准方法要计算二阶段精确成本 判断其可行性。交替切割策略的核心是先利用连续松弛 作为代理：
连续松弛下界。由于
若 ，则显然 ，无需求解混合整数子问题；直接根据子梯度生成切割
其中 为 在 处的子梯度。
精确评估。只有当 时，才求解混合整数二阶段子问题以获得 ，再按需生成标准整数最优性切割（6）。
2.2 交替切割算法
算法 3 对应的交替切割函数关键流程如下：
若当前 已在已评估集合 中，则 ，候选解可行。 否则若 未在连续松弛集合 中，则先计算 并加入 ；若 ，利用式（7）生成子梯度切割。 在 时，再计算 并根据是否 添加整数最优性切割（6）。 如果 ，则接受当前解。
该策略让连续松弛与混合整数求解交替进行，避免了大量无谓的整数求解。作者报告这一简单改动便能在文献实例中带来一个数量级的速度提升。
三、新的最优性切割与 CGLP 框架
3.1 上图像的几何构造
为改进传统整数最优性切割（6）的质量，作者分析了 二阶段期望成本函数 的上图像 的几何结构。设集合
是 的上图像。已评估的整数解集合 上，只有 的 值已知，其他 只能采用下界 。因此当前知识所能描述的上图像松弛集为
在仅考虑布尔可行域 的情况下，其进一步松弛为
图 1 对 且 时 的结构进行了示意，已知解对应的竖直射线构成对真实上图像的粗糙近似。
3.2 基于禁忌顶点问题的凸包逼近
作者指出，仅依赖标准切割（6）无法描述 的凸包，必须利用已知多个解的信息。其策略包括：
分解上图像。将 划分为已知部分与未知部分，并写为
其中
图 2 将这种分解进行了直观展示。
图2 上图像凸包分解为 PQ(V) 与 PL(V) （取自 Fig.3）
禁忌顶点递归。对于未知部分 ，作者借助禁忌顶点问题的思想，通过递归关系刻画其凸包结构。公式（8）指出，一个布尔向量属于 当且仅当其在前 维的投影不属于 ，或由 中向量通过翻转最后一位得到。
切割生成线性规划（CGLP）。基于上述结构，作者构造一个线性规划，其决策变量对应凸包分解中的权重，通过求解该程序可以生成同时考虑多个已知解的新型最优性切割。图 3 对比了标准切割和改进切割的差异，右侧灰色区域展示了新增信息提供的逼近效果。
3.3 CGLP 与新的最优性切割
在构造扩展公式并应用 Farkas 引理后，作者得到一个替代系统。由该系统的任一可行解 ，均可导出对 有效的不等式
为保证有限终止并在当前点 处紧致，作者引入紧致性条件，并证明在任意紧致解中必有 。因此可令 ，并得到最终的切割形式
该切割在 处是精确的，且被当前候选解 所违反。
3.4 实现与算法集成
与标准整数 L 型法的主要差异在于：在最优性切割阶段，用基于 CGLP 的切割（19）替代传统切割（6）。这要求维护一个已评估解集合 ，并在每次加入新解 后动态更新 CGLP。
算法 4 给出了基于 CGLP 的最优性切割函数，其流程与标准方法类似，但在 时，通过求解 CGLP 获得 并生成切割（19）。为避免每次从头构造 CGLP，作者提出基于禁忌顶点结构的增量更新策略，并在算法 5 中给出了对应的更新过程。
这些改进使得新切割能够同时利用多个已知解的信息，显著减少搜索树中重复出现的不可行整数解，从而提升整体求解效率。
四、综合算法与实验结果
4.1 综合方法
作者将交替切割策略与 CGLP 切割框架结合起来，形成改进的整数 L 型法。方法流程如下：
用连续松弛 进行快速拒绝，避免过早求解混合整数二阶段问题； 对于 未被连续松弛拒绝的候选解，求解混合整数二阶段问题，并利用 CGLP 生成新型最优性切割； 在主问题搜索树每个节点动态添加两类切割，逐步逼近 上图像的凸包； 当候选解满足 ，且未被任何最优性切割违反时，算法接受该解。
这种左右结构的结合（左边用连续松弛、右边用 CGLP 强化）既减少了评估次数，又提高了切割质量。
4.2 实验评估
论文在两个随机整数规划类别上进行了评测：随机服务器选址问题和随机多重 0–1 背包问题。实验比较了：
标准整数 L 型法； 仅采用交替切割策略的改进版本； 仅采用 CGLP 切割的版本； 将两种策略结合的综合方法。
结果表明：
交替切割策略显著减少了对二阶段混合整数问题的求解次数，从而将整体求解时间降低约一个数量级。 CGLP 切割在相同迭代次数下提供更紧的下界，搜索树规模明显缩小。 综合方法在多背包实例中平均运行时间比标准方法快 3～10 倍，在旅行商实例中加速更为明显。
这些结果验证了改进策略的有效性。
五、创新点与学术贡献
交替切割策略：首次在整数 L 型法中系统地利用 作为判断依据，减少昂贵的混合整数求解。
切割生成线性规划：借助禁忌顶点的几何分析，构建 CGLP，为已评估的多个解同时生成更紧的最优性切割，从理论上改善了上图像凸包的逼近。
综合左–右结构：将快速的连续松弛判定（左侧）与强大的 CGLP 切割（右侧）融合，使算法在不同阶段选择最合适的评估方式。
数值验证：在多个随机整数问题上验证了方法的实用性，显示出显著的计算优势和良好的可扩展性。
六、结论与展望
本文对整数 L 型法的两个瓶颈——昂贵的二阶段评估和低效的最优性切割——提出了系统改进。通过在候选解筛选阶段交替使用连续松弛判定，以及利用 CGLP 构造更紧的最优性切割，上图像被更有效地逼近，算法效率得到显著提升。未来可探索的方向包括：在多场景下自适应选择连续松弛或精确评估的策略；将 CGLP 框架推广到具有更复杂结构的随机整数问题；以及研究并行化技术以进一步提升算法的实际应用价值。
文章须知
链上镖师团队：常文婕（AEIC）、祁园园、汪朝杰、王一航、张仁义（EIC）、张晓乐
原文链接：http://dx.doi.org/10.1287/ijoc.2016.0695
原文链接见文末，或扫下方交流群二维码。群内实时更新推文及原文 pdf，方便专家学者随时获取（若二维码失效，请翻阅扫描最新文章的二维码）。
