共计 2967 个字符，预计需要花费 8 分钟才能阅读完成。
前言
最近意识到 对外输入才是王道，有几个益处：
- 便于从新梳理和思考，修补知识结构盲区
- 将内化转为外化，建设影响力
心愿每周都有更新，笔耕不缀。如有错漏，敬请雅正。
分支定界算法
分支定界法（branch and bound）是一种求解整数布局问题的最罕用算法。这种办法岂但能够求解纯整数布局，还能够求解混合整数布局问题。
分枝定界法的次要思路：以最大值问题为例，通常把全副可行解空间重复地宰割为越来越小的子集，称为分枝；并且对每个（松弛问题）子集内的解集计算一个 最优解 并尝试更新指标上界，满足整数束缚 可行解 时则更新指标下界，这称为定界。在每次分枝后，但凡界线超出已知可行解集目标值的那些子集不再进一步分枝，这样，许多子集可不予考虑，这称剪枝。
这个算法十分依赖于上下界的高效评估，如果没有上下界限度，整个算法就会进化到穷举搜寻。
The algorithm depends on efficient estimation of the lower and upper bounds of regions/branches of the search space. If no bounds are available, the algorithm degenerates to an exhaustive search.
如果以最大化问题为例，算法过程能够总结为如下步骤：
1. 初始化
首先通过启发式办法计算出一个可行解的目标值或负无穷赋值给 B（在最大化问题中下界 LB 与 B 等价）；初始化一个指标优化问题的队列，并将原始问题（A）入队列。例如，求解如下指标最大值，能够初始化 B 为 -inf。
$$
\begin{aligned}
&(A) \max S=5 x_{1}+8 x_{2} \\
&\left\{\begin{array}{l}
x_{1}+x_{2} \leq 6 \\
5 x_{1}+9 x_{2} \leq 45\\
x_{1}, x_{2} \geq 0 且为整数
\end{array}\right.
\end{aligned}
$$
2. 以后最优解及上下界更新
出队列，临时不思考整数约束条件，应用单纯形法在线性空间求解出一个最优解 x 及目标值 B ’。通过上下界的不断更新，一直实现分支操作和剪枝操作。
- 如果 x 存在不为整数且 B'<UB，领上界 UB=B’，并持续向下摸索，进入步骤 3；（注：不会存在 B ’>UB 的状况，因为分支后的解空间更小）
- 如果 x 取值均为整数且 B ’>LB，领下界 LB=B’，并记录下截至目前的最优解 x，该节点进行向下摸索；
- 如果 B’不在 [LB,UB] 之间，则能够认为以后节点下不会存在更优的参数组合，进行向下摸索，即，被剪枝（毕竟缩小了约束条件还不能超过以后的 LB，看来是没有心愿了；）
（注：下界由整数解管制，上界由线性解管制）
例如，不思考整数约束条件，A 转为 B0：(能够认为 A 式的解是 B0 解的子集)
$$
\begin{aligned}
&(B_{0}) \max S=5 x_{1}+8 x_{2} \\
&\left\{\begin{array}{l}
x_{1}+x_{2} \leq 6 \\
5 x_{1}+9 x_{2} \leq 45\\
x_{1}, x_{2} \geq 0
\end{array}\right.
\end{aligned}
$$
依据单纯形法求得 x1=2.25，x2=3.75，S0=41.25
3. 对节点进行分支
依据单纯形法求出的变量后果，抉择一个变量进行拆解：对最优解对应变量的前后整数作为拆分。
e.g. 将在 B0 拆解为 B1 和 B2，并将 B1、B2 放入队列；因为上一步松弛后最优解的 x2=3.75，原束缚改为 <= 3 和 >=4。(注：放入队列时，B1、B2 均带有“整数束缚”)
$$
\begin{aligned}
&\left(B_{1}\right) \max S=5 x_{1}+8 x_{2}\\
&\left\{\begin{array}{l}
x_{1}+x_{2} \leq 6\\
{5 x_{1}+9 x_{2} \leq 45} \\
\begin{array}{l}
x_{2} \leq 3 \\
x_{1}, x_{2} \geq 0 且为整数
\end{array}
\end{array}\right.\\
\end{aligned}
$$
$$
\begin{aligned}
&\left(B_{2}\right) \max S=5 x_{1}+8 x_{2}\\
&\left\{\begin{array}{l}
x_{1}+x_{2} \leq 6\\
{5 x_{1}+9 x_{2} \leq 45} \\
\begin{array}{l}
x_{2} \geq 4 \\
x_{1}, x_{2} \geq 0 且为整数
\end{array}
\end{array}\right.\\
\end{aligned}
$$
分拆后入队列的形式能够分为广度优先搜寻、深度优先搜寻和最佳优先搜寻。
- Breadth-first search (BFS)：广度优先搜寻，就是横向搜寻，先搜寻同层的节点。再一层一层往下。这种搜寻能够用 FIFO queue 实现。
- Depth-first search (DFS)：深度优先搜寻，就是纵向搜寻，先一个分支走到底，再跳到另一个分支走到底。这种搜寻能够用 LIFO queue 也就是栈实现。
- Best-First Search：最佳优先搜寻，最佳优先搜索算法是一种启发式搜索算法（Heuristic Algorithm），其基于广度优先搜索算法，不同点是其依赖于估价函数对将要遍历的节点进行估价，抉择代价小的节点进行遍历，直到找到指标点为止。这种搜寻能够用优先队列 priority queue 来实现。
4. 终止断定：队列为空时，完结计算。
维基百科的介绍：（最小化问题）
- Using a heuristic, find a solution xh to the optimization problem. Store its value, B = f(x_h). (If no heuristic is available, set B to infinity.) B will denote the best solution found so far, and will be used as an upper bound on candidate solutions.
- Initialize a queue to hold a partial solution with none of the variables of the problem assigned.
- Loop until the queue is empty:
3.1. Take a node N off the queue.
3.2. If N represents a single candidate solution x and f(x) < B, then x is the best solution so far. Record it and set B ← f(x).
3.3. Else, branch on N to produce new nodes Ni. For each of these:
3.3.1. If bound(N_i) > B, do nothing; since the lower bound on this node is greater than the upper bound of the problem, it will never lead to the optimal solution, and can be discarded.
3.3.2. Else, store Ni on the queue.
参考
几篇比拟不错的文章：1，2，3