个人知识库

外观

分支定价（Branch-and-Price） ​

分支定价算法是分支定界（Branch-and-Bound）与列生成（Column Generation）的结合，用于求解大规模整数规划问题。

1. 基本思想 ​

当列生成结束后，如果最终 RMP 的线性松弛最优解含有小数，说明我们遗漏了一些关键的基变量。要找到最优解，关键在于找到这些"漏网之鱼"（即被遗漏的最优基中的基变量），并将其加入 RMP。

1.1 识别"捣蛋鬼" ​

基于当前的最终 RMP，已经无法再找到新的具有负检验数的列。此时，我们需要将 RMP 中的"捣蛋鬼"识别出来：

"捣蛋鬼"：当前 RMP 的线性松弛最优解中取值为小数的列。

将其剔除后，形成新的 RMP，然后接着用列生成算法，基于新的 RMP 再生成若干新列。

1.2 关键问题：小数的列一定不是最优基变量吗？ ​

答案是不一定。

取值为小数的列也有可能会出现在全局最优整数解中，只是因为我们没有完整地将最优基中的基变量生成出来，导致这部分最优基变量与非最优基变量组成的 RMP 的整数可行解的凸包没有包含原问题的最优解，所以这部分最优基变量取值为小数。

1.3 剔除"捣蛋鬼"能保证最优吗？ ​

答案依然是不能。

当前 RMP 中取值为小数的列，同样有可能是原问题最优基中的基变量。如果将其删去并且禁止之后的列生成过程中再生成该列，一旦禁止的这一列正好是最优基中的基变量，那么最终得到的 RMP 的整数可行解的凸包就不能包含原问题的最优整数解。

1.4 分支定价的解决方案 ​

为了保证最优性，我们需要进行分支定界：

  1. 分支操作：针对取值为小数的列，分两种情况讨论：

    • 情况A：该列被禁止（剔除出 RMP，后续不再生成）
    • 情况B：该列必须包含（强制保留在 RMP 中）

  2. 以上两种情况包含了所有的可能，保证了没有排除任何整数可行解。

  3. 循环过程：

    • 在每个节点处，首先基于父节点的 RMP 做分支操作
    • 然后执行列生成算法，生成一些额外的新列
    • 不断地更新上界、下界和分支
    • 如果再次产生小数解，用相同的方法再执行一次
    • 直到遍历完成所有的可能，得到整数最优解

核心思想

分支定价算法 = 分支定界 + 列生成

  • 每次产生小数解后，执行分支操作（分两种情况讨论）
  • 在每个节点处，基于父节点的 RMP 做分支，然后执行列生成
  • 经过不断更新上下界和分支，最终得到原问题的最优解

2. 完整算法流程 ​

2.1 算法主要步骤 ​

分支定价算法的主要思路如下：

  1. 初始化：为 RMP 生成一些初始的列，并构建初始限制性主问题

  2. 求解松弛问题：求解 RMP 的线性松弛，得到对偶变量

  3. 列生成：根据对偶变量更新子问题目标函数，求解子问题，得到一些检验数为负的列，将其加入 RMP 中

  4. 循环迭代：循环步骤（2）和（3），直到没有新的检验数为负的列生成为止

  5. 整数性检查与分支：

    • 求解最终的 RMP 的线性松弛
    • 如果得到了整数解：算法结束，返回最优解
    • 如果解不是整数：进行分支，创建子节点以及对应的子节点的模型，更新上界（UB）和下界（LB），并在每个节点循环步骤（2）和（3）
    • 直到 BB tree 中的叶子节点集合为空，或者上界和下界相等，算法终止

重要说明

在创建分支子节点时，首先需要执行分支约束对应的操作（比如说将分支的列从 RMP 中删除），并在该节点的子问题中加入相应的分支约束。然后，可以保留该子节点的 RMP 中剩余的列，在此基础上，继续执行列生成算法，生成新的列，并加入该子节点的 RMP 中。

3. VRPTW 的分支定价建模 ​

3.1 基于路径的建模方式 ​

本节介绍如何用分支定价算法求解带时间窗的车辆路径问题（VRPTW）。

问题描述：

  • 顾客集合
  • 所有车辆同质（容量等参数相同）
  • 表示所有可行路径的集合（满足时间窗约束和载重约束）

关键说明： 中的元素可能非常多。如果每个节点的时间窗都非常大，那么 中的元素个数会随着顾客数量的增大呈现阶乘级别的增长。

决策变量：

其中， 是一条完整的从 depot（点 0）出发，最终回到 depot 的闭合路径。路径 的成本（长度）为 。

3.2 基于路径的完整模型 ​

VRPTW 的基于路径的模型可以写成下面的集分割问题（Set Partitioning Problem）：

其中， 是一个参数：如果顾客 在路径 中被访问到了，那么 ，否则 。

3.3 列生成建模 ​

当所有可行路径集合 中的元素数量非常庞大时，我们很难直接穷举出完整的 。一个可行的做法是：

  1. 先列出一些初始的可行路径
  2. 使用列生成算法，用循环的方式动态地寻找新的可行路径
  3. 将其添加到限制性主问题（RMP）中

3.3.1 限制性主问题（RMP） ​

基于当前已经列出的可行路径集合 构造的模型：

为了给子问题提供对偶变量的取值信息，需要将 RMP 松弛成线性规划，将约束 (7) 松弛为：

RMP 的线性松弛可以写成：

求解 (9)-(11)，我们可以得到约束 (10) 对应的 个对偶变量 。

3.3.2 子问题（定价问题） ​

VRPTW 的子问题就是寻找一条检验数为最小且为负的列，即子问题的目标函数为：

注意

这里是在所有可行路径 中去寻找检验数最小的路径，而不仅仅是当前已知的 。

所有可行路径的集合 其实是由一系列约束的可行域描述的，具体来说，就是由子问题的模型描述的。该子问题就是一个带资源约束的基本最短路问题（ESPPRC）。

ESPPRC 的模型可以写成：

其中：

  • ：所有节点集合（包括 depot 和顾客）
  • ：顾客 的需求量
  • ：车辆容量
  • ：从节点 到节点 的行驶成本
  • ：从节点 到节点 的行驶时间
  • ：到达节点 的时间
  • ：节点 的时间窗
  • ：一个大正数

4. 分支策略 ​

前面的章节中详细描述了分支定价算法的具体流程，但在分支策略的部分并没有进行详细的阐述。本节具体介绍几种典型的分支策略。

4.1 分支定价的特殊性 ​

分支定价算法中的分支操作和一般的分支定界算法中的分支策略还是有一些不同的。在分支定价算法中，主问题的变量和子问题是有一定关联的。

我们求解 RMP，得到了小数解，如果针对 RMP 中的变量进行分支，要想在子节点中被禁止的列不再出现，那就需要在子问题中也加入相应的分支约束。因此，分支定价算法中的分支，是"牵一发而动全身"的。

4.2 分支变量的选择 ​

在 VRPTW 的 BB tree 的一个节点处，用列生成算法生成了所有检验数为负的列，然后求解最终的 RMP 的线性松弛，得到了最优解 。

  • 如果 是整数，则不用分支
  • 如果 是小数，我们就需要针对 进行分支

选择分支变量：

是当前 RMP 的所有决策变量取值中分数部分最不可行的决策变量对应的路径（也可以是取值最接近 0.5 的路径）。假定 的取值为 ，我们就取变量 为分支变量。

4.3 基于路径的分支 ​

左分支（禁止路径）：

在左分支中禁止路径 被生成，只需要加入一个约束：

其中， 为路径 中包含的顾客点的个数，并且要将 对应的列以及 从左分支的 RMP 中删去。

右分支（必须生成）：

为了保证 一定被生成，我们可以将 保留在右分支的 RMP 中，并且在右分支的子问题中，删去 中的所有顾客点。

缺点：

这种分支方法非常不好，会导致左右子树非常不平衡：

  • 左分支：仅加入了一条约束，模型变化微小
  • 右分支：删去了若干顾客点，问题规模明显减小，求解难度明显减小

正是由于这个原因，基于路径的分支一般不被采用。

4.4 基于弧段的分支 ​

基于弧段的分支是实际中常用的一种分支策略，该分支策略下，左右子树相对较为平衡（Desaulniers et al., 2006）。

理论依据：

由于 ，且 RMP 的约束右端项全部为 1，因此在 RMP 的其他所有列中，一定至少存在一列，该列对应的路径中至少包含了路径 中一个客户点。即，RMP 中一定有至少一条其他路径至少包含了客户集合 中的一个客户点。

分支弧段的选择：

穷举 RMP 中所有已经生成的列，选择第一条满足下面条件的路径 作为要生成分支弧段的路径：

  2. 与路径 至少有一个重合的顾客点

然后选择 作为分支弧段，其中 是满足 的最小下标。

示例：

假设从 RMP 中抽取出 4 列，对应的路径为：

对应的决策变量 的取值为：

选择的分支变量为 ，对应的路径为：

中访问的所有点的集合为 ，其中客户点 2 除了在 中，在 中也被访问到了。

选择第一个与其至少共享一个节点并且至少有一个点不同的路径，因此选择：

路径 和路径 共享客户点 2，路径 包含点 2 但是不包含弧段 和 ，我们可以选择弧段 当作分支弧段（当然也可以选择 ）。

分支规则：

  • 第 1 个分支（左分支）：弧 被禁止访问

    • 在 RMP 中：将列 及对应的列删去
    • 在子问题中：添加分支约束

  • 第 2 个分支（右分支）：保证顾客点 1 和 2 只有被连续访问（弧 被选中）时，才能被同时加入

    • 禁止：进入顾客点 2 但不是从顾客点 1 进入的弧
    • 禁止：从顾客点 1 出去但不是到顾客点 2 的弧

4.5 改进的基于弧段的分支策略（推荐） ​

上面介绍的基于弧段的分支策略略微有些烦琐。接下来介绍另一种更易理解的基于弧段的分支策略（Feillet, 2010）。

参数定义：

  • ：如果路径 中包含弧 ，则 ，否则
  • ：表示弧 在当前节点的 RMP 线性松弛问题的最优解中被选中的次数（弧上的流量），显然

分支弧段的选取：

选取 最接近 0.5 的弧段作为分支弧段，并令该弧段为 。

分支约束：

  • 左子节点：，即在左子节点的 RMP 中加入分支约束

  • 右子节点：，即在右子节点的 RMP 中加入分支约束

优点：

这种分支约束更易于理解和实现，也更简洁：

  • 仅在左右分支节点中各添加了一条约束
  • 子问题不用做任何改动
  • 相比第一种基于弧段的分支策略，左右子树更加平衡

推荐使用

在实际中更建议使用第二种基于弧段的分支策略（Feillet, 2010）。

子问题的可选加速：

在第二种基于弧段的分支策略下，子问题也可以做相应的改动以加快求解：

  • 在左子节点的子问题中：删去弧
  • 在右子节点的子问题中：删去弧 （其中 ）和 （其中 ）

5. 界限更新 ​

在分支定价的过程中，采用最基本的界限（Bounds）更新。具体来讲，在每步的迭代中：

上界（Upper Bound）：

下界（Lower Bound）：

其中：

  • ：RMP 的整数可行解对应的目标值
  • ：RMP 的线性松弛问题 RLMP 的最优解对应的目标值
  • ：子问题 的最优目标值，即子问题 的检验数
  • ：子问题的数量（对于单车辆类型问题，）

5.1 界限的含义 ​

界限说明更新时机
UB（上界）当前找到的最好的整数可行解的目标值当 RMP 求解得到整数解时
LB（下界）当前节点能达到的最优值的下限估计每次列生成结束后

5.2 最优性判断 ​

当满足以下条件时，算法终止：

此时当前找到的整数可行解即为全局最优解。

剪枝条件

在分支定价的搜索树中，当某个节点的下界 时，该节点可以被剪枝（Pruning），因为该节点无法产生比当前最优解更好的解。

备忘 ​

（在此补充 ESPPRC 求解方法、加速技巧等实现要点。）

个人笔记

Copyright © yupli