分支切割法 好的，我们开始学习“分支切割法”。我将为你系统地梳理这个概念，从最基础的问题背景开始，循序渐进地深入到其核心思想、步骤细节和关键要点。 第一步：理解问题根源——整数规划 分支切割法是一种用于求解 整数规划 问题的高效算法。为了理解它，我们首先要明确它要解决什么问题。 什么是整数规划？ 它是一种数学优化问题。目标是在满足一系列线性（或非线性）等式与不等式约束的条件下，最大化或最小化一个线性（或非线性）目标函数。 它与普通线性规划的关键区别在于：它要求 部分或全部决策变量必须取整数值 （例如，0, 1, 2, ... 或者只取0和1）。 为什么需要专门的方法？ 如果我们忽略变量的整数要求，先求解对应的“松弛”线性规划问题，然后将得到的解进行简单的“四舍五入”，通常 无法 得到可行的整数解，或者即使可行也不是最优解。 因此，我们需要一套能够系统搜索整数解并证明其最优性的方法。 第二步：方法基石——分支定界法 分支切割法建立在“分支定界法”的框架之上。理解分支定界是理解分支切割的前提。 核心思想 ：将复杂的整数规划问题，分解成一系列规模更小、约束更严格的 子问题 ，并利用“定界”来避免穷举所有可能的整数解，从而高效地搜索最优解。 基本步骤 ： 松弛 ：对于一个待求解的整数规划问题，我们首先 忽略其整数要求 ，得到一个“线性规划松弛问题”。这个松弛问题更容易求解（例如，用单纯形法），其最优解提供了一个 下界 （对最小化问题）或 上界 （对最大化问题）。 分支 ：如果松弛问题的最优解中，某个本应取整的变量x取值是分数（比如x=4.3），那么原问题的任何可行整数解必然满足 x ≤ 4 或 x ≥ 5 。我们无法同时满足这两个矛盾的条件。因此，我们可以 将原问题分解为两个子问题 ，一个增加约束“x ≤ 4”，另一个增加约束“x ≥ 5”。这就像一棵树的根部分裂出两个树枝。 定界 ：对每个子问题，继续求解其线性规划松弛。如果某个子问题的松弛解是整数解，且目标值优于当前已知的最佳整数解，就更新“当前最优解”和“全局界限”。如果子问题的松弛解目标值比当前已知的最优整数解还差，那么包含这个子问题的任何整数解都不会更好，这个“树枝”就可以被 剪枝 （不再继续分解），节省了大量计算。 迭代 ：不断选择尚未处理的子问题进行分支、定界，直到所有分支都被处理（要么找到整数解并被记录，要么被剪枝）。 第三步：引入“切割”——分支切割法的核心创新 分支定界法在很多时候是有效的，但当问题规模很大时，分支树可能爆炸性增长，计算会变得非常慢。分支切割法的核心贡献在于，它在分支定界框架中，巧妙地引入了“切割平面”。 什么是“切割”？ 切割，也叫割平面，是一个 线性不等式 。 它有一个至关重要的性质： 任何可行的整数解都满足这个不等式，但当前线性规划松弛问题的最优（分数）解却不满足它。 “切割”的作用是什么？ 缩小可行域，收紧松弛 。当我们求解松弛问题时，其可行域包含了所有整数解，也包含了大量分数解。切割的作用就是“切掉”一部分不包含任何整数解的分数解区域，特别是包含当前非整数最优解的区域。 形象地说，如果把松弛问题的可行域看作一块包含所有整数点（小石子）的大面团，当前松弛解是面团里一个非整数点。切割就像一刀切下去，把这个非整数点所在、且不包含任何整数点的“面团角落”切掉，使得剩下的“面团”（新的松弛可行域） 更紧密地包裹着那些整数点 。 由于可行域被收紧，新松弛问题的最优解的目标值会 变差 （对最小化问题，下界会上升；对最大化问题，上界会下降）。这使上下界更加接近，从而在分支定界过程中能 更早、更有效地进行剪枝 ，大大减少需要探索的分支数量。 第四步：分支切割法的完整工作流程 现在，我们将“切割”步骤嵌入到分支定界框架中，就得到了完整的分支切割法。 预处理与初始松弛 ： 对原整数规划问题进行预处理（如简化约束、增强系数）。 忽略整数约束，建立初始线性规划松弛问题，并求解。记录其解和目标值作为初始界限。 主循环（节点处理） ： 从分支树中选择一个尚未处理的节点（子问题）进行探索。 求解松弛 ：求解该节点对应的线性规划松弛问题。 可行性/界限检查 ： 如果松弛问题不可行，该节点被剪枝。 如果松弛问题的最优值不优于当前全局最优整数解的目标值，该节点被剪枝。 整数性检查 ： 如果松弛解满足所有整数约束，则找到了该节点下的一个整数可行解。更新当前全局最优解（如果它更优），然后剪枝该节点。 切割平面生成 ： 这是关键步骤 。如果松弛解是分数解，算法会尝试 生成一个或多个有效的切割平面 。 将这些切割平面作为新的约束，添加到当前节点的松弛问题中。 重新求解 添加了切割后的松弛问题。这个“求解-生成切割-再求解”的过程可能会迭代多次，直到在可接受的时间内无法生成新的有效切割，或者收紧效果不再明显。 分支 ： 在处理完切割后，如果当前节点的松弛解仍然不满足整数要求，则像标准分支定界法一样，选择一个分数变量进行分支，创建两个新的子问题节点，加入到待处理列表。 终止 ： 当没有更多待处理的节点时，算法终止。 此时，当前记录的最优整数解就是原整数规划问题的 全局最优解 。如果整个过程中没有找到任何整数解，则原问题不可行。 第五步：关键要点与常见切割类型 核心优势 ：通过动态生成定制化的切割平面，显著收紧松弛问题的界限，从而极大地提升了纯分支定界法的求解效率。它是现代商用整数规划求解器（如CPLEX, Gurobi）的核心算法之一。 切割的有效性 ：一个好的切割应该“深”，即能尽可能大地提高松弛问题的目标值。同时，生成切割的计算成本不能太高。 通用切割 ： Gomory割 ：这是最早提出、理论上最重要的切割。它可以从单纯形表的最终表中直接生成，保证在有限步内收敛到整数最优解。但在实践中，纯Gomory割效率不一定最高。 针对特定问题的切割 ： 对于 0-1背包问题 ，有覆盖割、背包覆盖割等。 对于 旅行商问题 ，有子回路消除约束（可视为切割）、梳子不等式等。 对于 集合覆盖/划分/包装 问题，有覆盖割、背包割等。 现代求解器会混合使用多种通用和针对问题的切割策略。 总结一下 ： 分支切割法 是一个将 分支定界 的搜索框架与 切割平面 的紧化技术相结合的高效整数规划求解算法。其基本逻辑是：在系统搜索（分支）的过程中，不断通过添加自定义的约束（切割）来排除不含整数解的非最优区域，从而大幅缩小搜索空间，加速收敛到最优整数解。理解它，需要依次建立整数规划 -> 分支定界 -> 切割平面 -> 两者融合的知识链条。