关于人工智能:运筹优化中的分支定界算法

前言

最近意识到对外输入才是王道，有几个益处：

• 便于从新梳理和思考，修补知识结构盲区
• 将内化转为外化，建设影响力

心愿每周都有更新，笔耕不缀。如有错漏，敬请雅正。

分支定界算法

分支定界法（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.终止断定：队列为空时，完结计算。

维基百科的介绍：（最小化问题）

1. 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.
2. Initialize a queue to hold a partial solution with none of the variables of the problem assigned.
3. 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