分支定界算法

分支定界（Branch and Bound, BB）算法是求解整数规划（IP）问题的经典方法。

算法步骤

用分支定界算法求解 max 的 IP 问题的一般步骤如下（≤ 约束）：

▶ 分支定界算法步骤

1. 初始化

求得原问题线性松弛模型的最优解，作为节点 1。

2. 设置上下界

在节点 1 处：

• 将线性松弛的最优解作为 UB（上界）
• 将线性松弛的解向下圆整获得的解作为 LB（下界）

3. 选择分支变量

选择分数部分最大的小数变量进行分支，构建两个将可行域按照变量的整数限制分割成两个子区域的分支约束：

• 构造一个 ≤ 约束
• 构造一个 ≥ 约束

4. 创建分支节点

在 BB tree 里创建两个新的节点：

• 一个是对应 ≥ 约束的节点
• 另一个是对应 ≤ 约束的节点

5. 求解子问题

求解这两个新的节点处的线性松弛模型。

6. 更新上下界与剪枝判断

• 松弛的解是每个点的 UB
• 已经得到的整数解（在任意节点上）是 LB
• 根据查明的条件，判断该节点是否已被查明（剪枝）

7. 最优性判断

当一个节点得到了一个整数解，并且该节点的 LB 大于或者等于其他任何叶子节点的 UB 时（也就是大于或等于全局 UB 时），我们就求得了全局最优整数解。如果该节点的解不是整数解，我们就从所有节点中 UB 最大的节点处开始分支。

8. 迭代

回到步骤（3），继续分支过程，直到找到最优解或所有节点都被查明。

算法流程图

求解线性松弛
    ↓
设置初始 UB/LB
    ↓
选择分支变量 → 创建两个子节点（≤ 和 ≥ 约束）
    ↓
求解子节点线性松弛
    ↓
更新 UB/LB，判断剪枝条件
    ↓
找到最优整数解？
   /        \
  是        否
  ↓          ↓
结束      选择 UB 最大节点继续分支

关键概念

术语	说明
UB (Upper Bound)	上界，由线性松弛解给出
LB (Lower Bound)	下界，由找到的整数解给出
剪枝 (Pruning)	当节点的 UB ≤ 全局 LB 时，该节点无需再分支
分数变量	线性松弛解中取值为非整数的变量

---

分支策略

选择不同的分支变量会影响求解效率。以下是几种常见的分支变量选择策略：

1. 最不可行分支（Most Infeasible Branching）

选取变量取值的分数部分最接近 0.5 的变量作为下一个分支变量。

2. 最大分数值分支（Max Fractional Value Branching）

取最大分数值对应的变量作为分支变量。该方法甚至比随机选取还差，一般不推荐使用。

3. 伪检验数分支（Pseudo Reduced Cost Branching）

通过启发式方法近似评估约束的对偶价格，从而近似评估变量的检验数（因此叫伪检验数），最后根据伪检验数来评估变量分支对目标的影响，以影响大小为基准来选择分支变量。

4. 强分支（Strong Branching）

在分支之前首先估计哪个分支会给目标函数带来最大的改进，然后选该变量进行分支。

5. 伪成本分支（Pseudo Cost Branching）

在分支的过程中记录每个被选择的分支变量 分支前后的目标函数的变化，在当前时刻选择下一个分支变量时，根据每个取值为小数的变量的以往的分支相关信息，选择预期会给目标函数带来最大单位改善的变量作为下一个分支变量。

---

节点遍历策略

在 BB tree 搜索的过程中，选择 UB 最大的未被探明的叶子节点为下一个分支节点并不总是最好的。以下是几种常见的节点遍历策略：

策略	描述	特点
深度优先搜索（Depth First Search）	优先探索深层节点	能够更快地找到可行解
广度优先搜索（Breadth First Search）	按层级探索节点	可以更快地剪掉更多的分支
最好界限优先搜索（Best First Search）	LB 或 UB 最好的节点首先被探索	通常能更快找到最优解
其他启发式规则	结合具体问题特点的自定义策略	灵活性强