整数编程第五章--分隔符

最编程 2024-04-20 11:11:02

...

对于一个较复杂的 $\mathcal{NP}$ -hard问题（没有特别好的数学性质直接求解），如果你在寻找一种精确求解的方法，那一定绕不开分支定界法（Branch and Bound）以及它的变种，因为几乎所有的精确求解方法都建立在分支定界的框架之上。在掌握分支定界法之后，我们可以在分支定界框架上添加各类tricks，如割平面方法、启发式算法、预求解等等，也可以衍生出分支割（Branch and Cut）、分支定价（Branch and Price）等新精确求解框架。

一、隐式遍历（implicit enumeration）

figure-6.1.png

在第四章中我们提到，分支定界法运用了分解（decomposition）与隐式遍历（implicit enumeration）的思想，回顾以下命题：

Proposition (decomposition-bound)：Let $S=S_1\cup S_2\cup \dots \cup S_k$ , $Z^k = max\{cx\ :\ x\in S_k\}$ , $\overline{Z^k}$ be an upper bound on $Z^k$ and $\underline{Z^k}$ be a lower bound on $Z^k$ . Then $\overline{Z}$ = $max_k\ \overline{Z^k}$ , $\underline{Z}$ = $max_k\ \underline{Z^k}$ .

从上述命题中我们想到，可以利用上界和下界进行剪枝，从而达到隐式遍历的效果。而线性松弛是一个得到上界的方法，因此我们在每个节点得到并求解线性松弛子问题，再利用上述命题更新主问题的最优解、上界与下界，通过上下界来进行剪枝，完成隐式遍历。

Pruned by optimality:
当某一分支已达最优解（上下界相等）时，无需再对该分支进行分解。以下是一个例子：

S为主问题，目前已知S的上界 $\overline{Z} = 27, \underline{Z} = 13$ ，将S分解为 $S_1,S_2$ 两个子问题，解出子问题的上下界，则子问题带来的新上下界为 $\overline{Z} = max_k\ \overline{Z_k} = max\{20,25\} = 25$ 与 $\underline{Z} = max_k\ \underline{Z_k} = max\{20,15\} = 20$ 。新的上下界（20，25）相较于之前的上下界（13，27）明显更优（上下界更加逼近了），因此更新新上下界为 $\overline{Z} = 25, \underline{Z} = 20$ 。
接下来我们考虑剪枝的可能性，由于 $S_1$ 上下界相等，已经是最优解了，所以 $S_1$ 剪枝。

figure-6.2.png

Pruned by bound：
当某一分支的上界小于主问题的下界时，该分支不可能再对上下界改进，因此无需再对该分支进行分解。以下是一个例子：

S为1中一样的主问题，子问题带来的新上下界为 $\overline{Z} = max_k\ \overline{Z_k} = max\{20,26\} = 26$ 和 $\underline{Z} = max_k\ \underline{Z_k} = max\{18,21\} = 21$ ，更新主问题上下界为（21，26）。
由于 $S_1$ 的上界小于主问题的下界，因此将 $S_1$ 剪枝。

figure-6.3.png

Pruned by infeasible：
当某一分支无可行解时，显而易见的，无需再对该分支进行分解。

二、B&B（Branch and Bound）算法流程

figure-6.4.png

分支定界法在每个未被剪枝的节点 $S$ 或 $S_i$ ，都要进行Bounding、Pruning和Branching三个步骤：

Bounding. 解该节点的LP松弛问题，得到最优值 $p^*$ ，与最优解 $(\overline{x_1},\overline{x_2},\dots, \overline{x_n})$ 。更新该节点的上界为 $\overline{Z} = p^*$ ，下界为 $\underline{Z} = -\infty$ ；

若最优解 $(\overline{x_1},\overline{x_2},\dots, \overline{x_n}) \in \mathcal{Z}^n_{+}$ ，则最优解是一个整数可行解，提供下界。更新该节点的下界为 $\underline{Z} =p^* = \overline{Z}$ ；

更新全局 $upper\ bound = max\{upper\ bound, \overline{Z} \}$ ， $lower\ bound = max\{lower\ bound, \underline{Z} \}$ ；
Pruning. 利用pruned by optimality/bound/infeasibility进行剪枝；
Branching. 在未被剪枝的节点上选择某一变量 $x_j$ （一般选择非整数的变量）进行子问题分解，如果 $x_j$ 的LP松弛解为 $\overline{x_j}$ ，则分支为：

$\begin{aligned} &S_1 = S \cup \{x\ :\ x_j \leq \lfloor \overline{x_j} \rfloor \}\\ &S_2 = S \cup \{x\ :\ x_j \geq \lceil \overline{x_j} \rceil \} \end{aligned}$

三、Branch and bound算法示例
$\begin{aligned} S = max\ &4x_1 - &x_2 & &\\ &7x_1 - &2x_2 &\leq &14\\ & &x_2 &\leq &3 \\ &2x_1 - &2x_2 &\leq &3 \\ & & x &\in &Z_{+}^2 \end{aligned}$

求解原问题的LP松弛问题可得： $\overline{x} = (2.86,3)$ ， $p^* = 8.429$ 。更新全局upper bound = 8.429，lower bound = $- \infty$ 。
针对 $x_1$ 进行分支，得到 $S_1$ 与 $S_2$ ，分别加上约束 $x_1 \leq 2$ 和 $x_1 \geq 3$ .
$\begin{aligned} S_1 = max\ &4x_1 - &x_2 & &\\ &7x_1 - &2x_2 &\leq &14\\ & &x_2 &\leq &3 \\ &2x_1 - &2x_2 &\leq &3 \\ & & x &\in &Z_{+}^2 \\ & & x_1 &\leq &2 \end{aligned}$

$\begin{aligned} S_2 = max\ &4x_1 - &x_2 & &\\ &7x_1 - &2x_2 &\leq &14\\ & &x_2 &\leq &3 \\ &2x_1 - &2x_2 &\leq &3 \\ & & x &\in &Z_{+}^2 \\ & & x_1 &\geq &3 \end{aligned}$
求解 $S_1$ 可得： $\overline{x} = (1,0)$ ， $p^* = 4$ .
求解 $S_2$ 可得： $S_2$ infeasible，prune by infeasibility。
更新全局upper bound不变，lower bound = 4。

在 $S_1$ 节点针对 $x_2$ 进行分支，得到 $S_3$ 和 $S_4$ ，分别加上约束 $x_2\leq 0$ 和 $x_2\geq 1$ .
$\begin{aligned} S_3 = max\ &4x_1 - &x_2 & &\\ &7x_1 - &2x_2 &\leq &14\\ & &x_2 &\leq &3 \\ &2x_1 - &2x_2 &\leq &3 \\ & & x &\in &Z_{+}^2 \\ & & x_1 &\leq &2 \\ & & x_2 &\leq &0 \end{aligned}$

$\begin{aligned} S_4 = max\ &4x_1 - &x_2 & &\\ &7x_1 - &2x_2 &\leq &14\\ & &x_2 &\leq &3 \\ &2x_1 - &2x_2 &\leq &3 \\ & & x &\in &Z_{+}^2 \\ & & x_1 &\leq &2 \\ & & x_2 &\geq &1 \end{aligned}$
求解 $S_3$ 可得： $\overline{x} = (1.5,0)$ ， $p^* = 6$ .
求解 $S_4$ 可得： $\overline{x} = (2,1)$ ， $p^* = 7$ .
更新全局upper bound不变，lower bound = 7。因为 $S_3$ 最优值6小于lower bound 7， $S_3$ is pruned by bound.

此时完成整棵树的遍历，得到的最优值为7，最优解为（2，1）。