分支定价切割（Branch-Price-and-Cut, BPC）
分支定价切割（BPC）在分支定价（Branch-and-Price, BaP）的基础上，进一步在搜索树各节点对限制性主问题（RMP）的线性松弛加入有效不等式（割），从而收紧下界、减少分支规模。可概括为：
与单纯的 Branch-and-Price 相比，BPC 在同一节点上既动态加列（定价），又动态加行（割）；与 Branch-and-Cut 相比，BPC 的主问题变量维数巨大且隐式表示，列与割均需在搜索过程中按需生成。
适用于什么问题
下列情形的整数线性规划或组合优化，常与 BPC（搜索结点上对限制性主问题同时「按需加列」与「按需加割」）相匹配：可选的路径、班次配对、切割模式、乘务轮转方案等数量庞大，无法用小规模紧凑 MILP 起步枚举全部列变量，必须靠定价子问题逐批生成列；与此同时，仅靠当前列集合下的线性松弛仍偏离整数最优值的凸包信息较远，还需一类或多类 割平面（与子回路、分支耦合切口等相关的不等式）在结点上收紧松弛边界。
典型应用领域包括但不限于：车辆与乘务路由（VRP / VRPTW 等）、机组配对（crew pairing）、切割 Stock/Gilmore–Gomory 模式生成后的整数选型，以及其他写成集合分割 / 集合覆盖形式的广义指派之类大而隐性变量的 formulation。不太适宜：变量一开始就数量有限且易于枚举的 MILP（优先考虑 Branch-and-Cut 或通用求解器即可）；或未用到大规模隐性栏生成的中小型整数模型。
1. 动机
1.1 仅分支定价时的局限
在 BaP 中，各节点上反复求解列生成，直至定价子问题不再产生检验数为负的新列（即当前 RMP 下最优性在列上已满足）。此时 RMP 的线性松弛解仍可能很松：
- 整数结构（子圈、度约束、时序等）的多面体凸包难以仅由已生成的列张成；
- 可行整数点的凸包与当前 RMP 的松弛可行域间隙大 → 需更多分支才能固定整数性。
割平面在不动态增加“列”的前提下，可切掉一批无整数最优的分数点，收紧当前节点的 LP 界。
1.2 与 Branch-and-Cut 的分工
| 特点 | Branch-and-Cut | BPC（Branch-Price-and-Cut） |
|---|---|---|
| 变量 | 通常显式、有限维或易枚举 | 列可能无法穷举（如巨多路径、模式） |
| 行（割） | 按需生成、加入 | 同样按需生成、加入 |
| 列 | 一般固定 | 列也在节点上动态加入（定价子问题） |
BPC 把 “加列” 与 “加行” 统一在同一树节点的迭代中：先（或交替）定价以改进列，再分离/添加割以改进松弛，直至满足定价终止与无割（或达到迭代上限）后再分支。
2. 节点上的典型迭代结构
在搜索树的某一节点，记当前 RMP 为对原问题某一分支约束下路径的限制主问题（变量为当前已出现的列/模式，约束含分支与已加入的割）。
典型内层循环：可理解为下述三步的迭代（文字叙述无歧义时也可写作「可理解为：」）。
列生成（定价）
给定当前 RMP 的对偶 （及与割、分支约束对偶的联合），解子问题；若存在检验数为负的列，加入 RMP，返回步骤 1。
注：加入新割后，对偶改变，往往需继续定价以恢复 LP 最优与对偶信息。割分离
在当前 RMP 的 LP 最优解上，我们寻找一条或多条有效的线性约束（Cuts）。这些约束能切掉当前的非整数解，但不会切掉任何可行整数解。若存在，加入 RMP，返回步骤 1（因约束集变化，通常需再跑列生成）。终止
当无新列、无新割（或仅割、列交替若干轮无改进）时，得到该节点的强化的 LP 界，再判断是否原问题整数；否则分支并继承/更新列池与割集（实现细节依代码架构而定）。
关键点：割的对偶会进入定价子问题的检验数计算（与 BaP 中仅分支对偶进入子问题相比，形式更复杂），子问题与 RMP 的紧耦合是 BPC 实现难点之一。
小结：在定价子问题中计算判别数（Reduced Cost）时，必须考虑割平面在 RMP 对偶里产生的对偶影响；若仍按仅主约束、分支的对偶来构造子问题目标，则判别数与 RMP 的 LP 对偶不一致，易误停列生成或漏加仍具负判别数的列。
3. 与分支定价、列生成的关系（小结）
- 分支：保证不丢任何整数可行解，最终收敛到最优整数解（在有限分支假设下，依算法正确性设计）。
- 定价（Price）：在隐式巨大变量集上，只生成有希望的列；
- 切割（Cut）：在不枚举全部变量的前提下，用少数线性不等式逼近整数可行解的凸包信息。
三者在同一框架中反复调用：并不是“先 BaP 跑完再割”，而是在节点上对同一 RMP 反复 Price ↔ Cut 直到稳定，再 Branch。
4. 节点内层循环（逻辑伪代码）
下面用节点指搜索树中对应一组分支（及祖先分支）的子问题；RMP 只含当前列，约束含原始紧凑形式经分解后的行、分支行、已添加的割。
在节点 v：
初始化列池、割集为继承自父节点（或本节点新启）
重复直到满足终止判据（无新列且分离失败，或时间/轮数限制）:
① 列生成：在当前 RMP 上求 LP 最优，得对偶 π；解定价子问题；
若存在检验数 < 0 的列，加入 RMP，继续 ①
② 若 LP 解已为整数，则本节点剪枝/更新并退出
③ 割分离：在当前 LP 解上运行分离算法，寻找违反的有效不等式；
若找到，加入 RMP，回到 ①（对偶与可行域已变，一般需重新定价）
若 LP 解分数且不再产生割，则分支（对分数变量/结构等），为每个子节点创建新节点并递归要点：加割与加列都会改变 RMP，二者交替直至该节点列池–割集在 LP 意义下稳定（工程上常设最大轮数防止振荡）。
5. 关键数学挑战：对偶变量的补偿
BPC 相对 BaP 的核心难点在于：RMP 中每增一条割平面，对偶会多出一类与割关联的乘子；在定价子问题里为候选新列 计算检验数 时，必须把这类乘子通过割在列上的系数显式补偿到检验数中，才能与 RMP 的 LP 对偶一致。若遗漏补偿项，会误以为检验数已全无负、提前终止列生成，造成漏列、界不紧甚至不收敛（与 §2 小结同一实质）。
先用一句话把握实质：仅分支定价时，检验数可写成「列费 减主约束对偶 在列上的冲销」；BPC 在 RMP 中多了割，对偶除了与主行对应的 外，还有与各条割对应的 ；在检验数中必须多减一项「」——割对偶 通过列在割里的系数 进入，这就是「对偶变量的补偿」。不加这一项，与 RMP 对偶不相容，割在数学上等于没写进定价子问题。
5.1 符号约定
- ：与原主问题中（经 Dantzig–Wolfe 等分解、聚合后出现在 RMP 里的）第 条约束对应的对偶（乘子）；
- ：与第 条新加入的割平面对应的对偶（乘子）；
- ：当前在定价子问题中考察或生成的一列（如一条路径、一个模式）；
- ：该列在目标中的直接费用（或经标准化后的列费用）；
- ：列 在第 条主约束（RMP 中对应行）中的系数；
- ：列 在第 条割中的系数（割在列/模式的系数向量上再施加一行线性式；具体是 还是 取决于 RMP 写法，符号与对偶的正负约定一一对应）。
说明：下式采用「最小化问题 + 对偶冲销」的最常用写法。若 RMP 里将约束写成另一种不等号方向（例如统一为 ），在实现上不必死记哪一个 取负号，唯一标准是：子问题中构造的检验数与 RMP 求得的对偶可行满足对偶关系（即与 LP 的 KKT/互补松弛一致）。
5.2 从分支定价到 BPC：检验数多出一项「割的补偿」
仅分支定价（BP、无割）时，在标准写法下，新列 的检验数为
即直接费用 减去主约束对偶 在列 的系数 上形成的冲销。
分支定价切割（BPC）在 RMP 中再引入割之后，同一条候选列的检验数在形式上多出一项——必须把各条割的对偶 与列在割中的系数 一同纳入：
其中 常被称为对偶的（割）补偿项：割的对偶 经 作用在列 上，与 、 同一层级地进入检验数；在实现中，这通常体现为合并进定价子问题目标的附加费用/附加资源项，而不是在代码里只更新 、却不把割写进子问题。
5.3 为何「难」： 与结构错位
难点在于：割是后加的， 并不保证能嵌入原问题的可递推结构。若割在列上的作用与定价子问题的「天然结构」（例如最短路/资源最短路/背包）不兼容：
- 当 仍能与网络/动态规划表等同构 时，有时可重新解释为「弧上加价、节点上加资源下界」等，继续在多项式可解的框架内定价；
- 当 与子问题的可分解结构无关、或打破了原有递推，定价问题可能从易解的（如简单最短路）剧变为在一般情形下难甚至 NP-hard 的组合问题。
因此，BPC 的算法设计，往往不仅要选强的割，还要问「这条割进来之后，定价还能按什么结构解？」——割的分离与子问题的可解性、可维护性是绑在一条绳上的。
5.4 与实现的衔接
每新加一条割、RMP 的 LP 重解之后，对偶向量从「主要是 」变为「 联合」。定价子问题在构造任何一列的检验数时，必须使用完整的「主约束对偶 + 割对偶」所有在子问题中可出现的分量；只用 、不用 ，即与上式不一致，会在逻辑上重复已讨论过的误停列生成问题。
小结（本节）：BPC 在数学上的清晰公式就是 的第三项 ；在实现上则落实为对偶数据流与子问题构造的一致——割、列、对偶三者缺一即可能错。
6. 割平面的分类：鲁棒与非鲁棒
上节指出：割在列 上的系数 决定「对偶 怎么进入 检验数」；在分解与 BPC 文献中，还常从对定价子问题结构的影响对割作二分类——是否仍能在 原有子问题模板上、只调边权/资源就完成检验数与列生成。这与 §5.3「 与结构错位」的叙述一一对应。
6.1 鲁棒割平面（Robust Cuts）
定义（直观）：割在列/模式系数上给出的 ，可以一一对应到原问题在子问题里使用的决策对象上——如边（弧）、点、已知的资源分量等；因而割对检验数的修正，在实现上等价于在不扩大状态空间的前提下，改弧权、加节点罚项、对某种累计量下界/上界等。
效果：不改变子问题可解的算法骨架（例如标号法/动态规划的递推形式仍成立）。以车辆路径为例，针对某节点集的割常只改变与穿越该集合相关的弧的等效成本；定价仍是「带资源的最短路/标号」一类问题，只是弧权随 更新，而非换一个完全不同的 NP-hard 黑箱。
常见例子：容量相关割中，许多形式可写成对进/出某子集的弧的线性组合；在列模型下 可追溯到路径是否使用某类弧，从而并入标号中的边费用与资源更新。子集行不等式（SRI 等）在精心嵌入时也可归入鲁棒可维护的一类（依具体 Dantzig–Wolfe 建模而定）。
与对偶补偿的衔接：对鲁棒割，对偶 在实现上往往体现为在子问题里调权、加资源——与 §5.2 的「 并入检验数 / 子问题目标」最顺手，仍要在代码里显式从 RMP 对偶传入，不可漏传。
6.2 非鲁棒割平面（Non-robust Cuts）
定义（直观）：割的系数 与子问题里自然生成的局状态（如「当前在何点、尚余何资源」）不直接同构；难以只用「弧上加价、节点上常数罚」等不增维的改动表达。
效果：破坏原有子问题的可递推结构。为忠实地反映完整的 ，常被迫给标号/状态增加新维度（去追踪与割相关的非局部、非可加量），状态数往往随问题规模与割的层次快速放大，计算量剧增。与 §5.3 一致：在一般情形下，原本的最短路/背包式子问题在不兼容的割下会变为难子问题。
常见例子（示意）：与列组合的强逻辑、Gomory 型在隐式列上的复杂线性式等；若不能改写为对边、局部可加的权，容易落入非鲁棒范畴。
与对偶补偿的衔接：非鲁棒不意味着可以不补偿 ——恰恰相反：仍须按 §5 的检验数公式完整计及 ；难在要在经扩展后的状态空间里仍能高效实现同一检验数公式，而非可省略割对偶。
6.3 分类小结
| 鲁棒割 | 非鲁棒割 | |
|---|---|---|
| 与子问题 | 易映射到边、点、可加资源 | 常与子问题的局状态不匹配、难以局部表出 |
| 对子问题结构 | 基本保持（标号/DP 骨架） | 常需扩状态 或 换 求解方式 |
| 对偶 进检验数 | 多表现为调权/资源 | 常需新维度才能表出 |
| 工程上 | 优先在设计 BPC 时选用/构造可维护的鲁棒族 | 少量强割精化，需权衡界与定价时间 |
统一前提：无论鲁棒与否，在定价中计算检验数时，由割产生的对偶（ 及相应的 ）都必须在子问题/检验数里显式体现；分类回答的是「体现方式」——同构改权还是扩维改模型——而非要不要对偶补偿。