1 从一个示例入手

原始题目：

分支定界的计算过程：

由上述示例可知:

在第一次分支时，我们的左侧分支得到的最优解是原问题的一个可行解，终止此分支，将其视为原问题的一个上界；右侧分支得到了-18.5的最优解，但不是原问题的可行解，继续对其进行分支，此时问题的界为【up = -16， lb = -18.5】

第二次分支时，左侧分支得到-17.4的可行解，但不是原问题的可行解，继续分支；右侧分支无可行解；此时问题的界更新为【up = -16, lb = -17.4】

第三次分支时，左侧分支得到原问题的可行解-17，停止搜索；右侧分支得到了-15.5的最优解，但不是原问题的可行解，且劣于之前确定的界限，停止搜索。

得到原问题的最优解为-17

分支定界算法的搜索过程是一个树结构的搜索，每次分支过程都是在解决原始问题的一个子问题。我们将原始的整数线性规划问题松弛为线性规划问题中，得到的线性规划问题的最优解就相当于分支的根节点，其作为所有分支节点的起点进行搜索；在完成一次分支后，如果得到的最优解是原问题的可行解，我们将停止对该分支进行继续搜索；如果不是原问题的可行解，我们会做一次上下界的检查，如果子问题不能产生更好的解，我们将会砍掉该分支；如果位于确定的上下界内，则继续对该分支进行搜索；当所有的分支都不能得到更好的解时，我们就认为得到了问题的最优解，算法即终止。显然，上述过程可以被视为一种目标明确的枚举过程。

2 关于松弛的你要知道的几个概念

松弛模型是为了针对离散优化变量指数级增长而设计的一种辅助性求解方法，其核心在于放松原问题的某些约束或目标函数，使之更易求解，确保对松弛问题的深入分析得到原问题的最优解。

对于整数规划问题，最好的松弛办法为将离散变量松弛为连续变量。

对于优化问题P和R而言，若问题P的可行解都是问题R的可行解，且R的最优解与P的最优解更优或相等，我们便将问题R称为问题P的松弛问题。

P和R的解空间如下图所示：

灰色椭圆为松弛问题最优解所处于的区域

黑点为原问题的最优解

白色椭圆为问题P的可行解范围

最外侧为松弛问题的解空间。

显然，我们可以得出如下结论：

松弛问题R的不行解，对于问题P绝对是不可行的；

如果松弛问题P的最优解是原问题P的可行解，则其必然是原问题P的最优解；

对于最大值模型，松弛问题R的最优解提供了原问题P的上界，且原问题的每一个可行解都可以作为原问题的一个下界；

对于最小值问题，松弛问题R的最优解提供了原问题P的下界，且原问题的每个可行解都可以作为原问题的上界；

3 算法框架

有了上面的知识铺垫，我们就可以对分支定界算法的算法进行系统全面的描述了。

3.1 基本框架

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.

英文看不懂，来个中文的：

再来一个更为直观的流程图：

3.2 三种搜索策略

广度优先策略（Breadth-first search，BFS）：横向搜索，将同层的节点搜索完毕之后，在进行下一次的搜索；这种搜索可以用FIFO queue实现。首先介绍三种搜索策略：

深度优先策略（Depth-first search, DFS）：纵向搜索，将一个分支走到底，然后再开下一个分支的搜索；这种搜索可以用LIFO queue也就是栈【后进先出】实现

最佳优先搜索（Best-First Search，BFS）：基于广度优先策略，先对同层节点使用估价函数对所有节点进行估价，选择估值最小的节点遍历，直至得到最优解位置。可使用优先队列priority queue来实现。