分支定界、分支切割、分支定价的区别

目录

1.从原理的角度

（1）分支定界：

（2）分支切割：

（3）分支定价：

2.从分支树的角度

（1）分支定界

（2）分支切割

（3）分支定价

---

1.从原理的角度

（1）分支定界：

是仅添加整数割（本质上是一种特殊的割平面）。

（2）分支切割：

是添加（根据问题）定制的割平面（规则/指标）。比如VRP问题中的k-paths割，即若干顾客的需求量至少需要的车辆数。

（3）分支定价：

将原问题重写，如VRP问题中将x_{ijk}的3-index模型改写为路径y_{r}的1-index模型（RMP）；然后松弛主问题得到RLMP，再根据子问题的检验数不断往RLMP中添加新的路径，再次求解RLMP直到求到RLMP的最优解。若该解是非整数解则分支。

该算法比前两者难的原因是，需要改写模型；而且需要求解子问题（设计出有效的算法，比如标签算法，支配规则等）。别的与前两者区别不大。

2.从分支树的角度

从分支树的角度，我觉得更好理解。

（1）分支定界

可以看到，通过定界和剪支操作，比全枚举（二叉树）要少了很多枝。

（2）分支切割

可以看到比着分支定界算法枝干又减少了，但是两个叶子节点之间多了一些点（蓝框），是通过红框中的cut而求解产生的新的点。

 （3）分支定价

可以看到它在叶子节点做了更多的工作，所以最终实际上的节点更少。

总结：难度系数，分支定界<分支切割<分支定价。难的点在于分支切割要找到有效的加强的割平面（cut）；分支定价需要重写模型，写出主问题和子问题，还需要求解子问题 。