Discrete Optimization (Coursera) week2-3 BnB求解背包问题

Branch and Bound

Branch and Bound (BB) is another powerful tool in discrete optimization （platitude一则）

我们继续以背包问题来介绍这一算法。

首先考察一个naive way in solving knapsack problem：现在有 1,2,…,n这么多个物品，那么对于物品1，我可以选择或者不选择---->这就分了两个岔，对于每个岔，对于物品2我都可以选择或者不选择---->这就分了四个岔… 我们其实只需要检查所有不同的选择，也不过就（？） $2^n$2n种组合。当n比较小的时候，其实穷举就行了，但是如果n比较大…（电脑：跑你????呢？）

那么，有没有方法可以减小需要验证的数量呢？例如，现在某一个分叉已经只有两个物品可以选择了，而所能获得的最大价值也不过10元，远远小于某一个分叉，which has ALREADY obtained 100元。那么，这种情况下，是不是可以直接将那个继续选下去也最多不过10元的分叉给砍掉呢？

基于这样的想法，BB被提出了。Branch指的还是分叉，Bound就是用一个最大值或者最小值来作为上界/下界。当某一个分叉1的最大值小于当前某个分叉2已经取得的值，那么显然分叉1就可以被砍掉了。这或许可以大大减小我们需要验证的数量！

关于 Bound: 如何找到上界或者下界？一个常用的方法就是将 decision variables的范围扩大，比如从整数域扩展到实数域（例如 {0,1} —> [0, 1])，这样既可以保证得到了上界/下界，也可以快速地求解（Linear Optimization problem is NOT a Problem. It’s highly mature! ）

The General Framework:

at a really high level, BnB is something like this: (w.l.o.g. Assume want to find the maximum of $f(x)$f(x))

---

1. 用某种粗糙的（heuristic）的方法找出一个解 $x_h$xh​，记下这个解的值 $f(x_h)$f(xh​)，记作 Bound。（如果找不到这样一个粗糙的方法，直接将 Bound 设为 $-\infty$−∞
2. 初始化一个 queue。并在其中填入一个 dummy solution: none of variables are assigned values (a partial solution)
3. Loop the following:
   1. 从queue中拿出一个node N
   2. 如果这个 solution为 x并且 $f(x) > Bound$f(x)>Bound，那么 x为目前找到的最优解，将 Bound 更新为 f(x)并记下这个解 x
   3. 如果这个node还不能称作一个合法的 solution，那么 branch N to new $N_i's$Ni′​s
      1. 如果 $Bound (N_i) \le Bound$Bound(Ni​)≤Bound，那么这个情况可以被忽视了，也没必要继续分叉了，因为再怎么折腾也没现存的最优解大┓( ´∀` )┏
      2. 反之，则将 $N_i$Ni​加入队列 queue

---

而BB又可以分为分为 Depth-first, Best-first, Least-Discrepency 三种（And more…）下面继续以背包问题进行进一步阐释。

Depth-first

这个方法就是尽可能地、贪婪地选择物品(going left)，这样可以很快地到达二叉树的底部，从而得到一个粗糙的估计，然后再倒回去考虑那些比较保守的、没有选择物品的分叉口。当那些分叉口的 bound比迄今所得到的值更小，即砍掉分叉。具体图示如下：

首先，初始化 value = 0, room = 10, estimate = 92(上界，在 linear relaxation下的最乐观估计)。

则先go left，即选择物品1，得到 value = 45, room = 5, estimate = 92, 记作 (45, 5, 92)。

继续 go left，可是现在已经装不下物品2了，因此 “stuck”。

所以只能go right，不选择物品2，现在得到新的上界，(45, 5, 80)。

继续go left，得到 (80, 2, 80)，这一分叉已经 run to the end。

返回 (45, 5, 80)，go right，得到 (45, 5, 45)，由于这个的 bound比现在已知的最优解(80)更小，所以排除这个分叉。

返回 (0,10,92)初始节点，go right，得到(0,10,77)，由于这个的 bound比现在已知的最优解(80)更小，所以排除这个分叉。

Best-first

这一策略通常比Depth-first表现差很多。

这个策略将优先考虑node with best estimation。剪枝发生且仅发生在所有的node都比现在已经找到的解更差。

Memory efficiency: Its a DISASTER
（大概是指数级别？）

Limited-Discrepancy Search

LDS是一开始绝对相信自己的直觉，后来越来越不相信。

比如，首先我们可能会觉得，最贪婪的是最吼的！所以遇到一个装一个进袋子，直到装不下为止。

然后我们可能会想，嗯… 万一放弃一个，从 n-1个中挑选是一个更好的主义呢？OK，那么就试试 go right only once in the tree。

… 以此类推，放弃 2, 3,…, n-1个…

当然，我们会将最优解记录下来并不断 update，当某一个分叉的 bound比现存最优解更烂，那么我们可以放心地 prune。

Memoery efficiency: depending on implementation, between DFS and BFS