割平面法python_解决纯整数规划分支定界法所面临的“组合爆炸”的关键是什么？...

关键有二：快速找到优质的可行解(upper bound，见3)

提高线性规划松弛解的质量(lower bound，见4)

1，假设整数变量是0，1变量，假设有n个binary ariable，那么分支定界的分支，最坏情况需要分2^n个分支(每个分支需要求解一次线性规划)，这就是指数(组合)爆炸！https://www.youtube.com/watch?v=jgQhzl3djM8

2，当然因为还有定界，定界就是定lower and upper bound.假设问题是minimization problem，那么upper bound是一个全局值，记录的是best feasible solution，lower bound记录的是当前所有分支LP relaxation的最小值。

那么这个算法最关键的地方来了，如果upper bound小于当前分支的lower bound，也就是说连LP relaxation都比当前的feasible solution要差，那么加上整数约束以后肯定更差，所以这个分支已经可以砍断了(prune)！这样一来，就可以减少很多需要访问的分支的数量！

关于整数规划的精确解法--分支定界法，参见：

3，从2也可以看出一个好的feasible solution的重要性。如果能一开始就给出一个好的feasible solution(upper bound)，那么能极大减少需要访问的分支数量。

而提供feasible solution的方法有很多，比如自己写个heuristic，一般是greedy的。或者可以用meta heuristic找到它所能找到最好的，作为整数规划的初始解。

另外一个思路是，已经开始分支定界了，在得到LP solution以后做简单的rounding，试图找到与他临近的feasible solution。

当然还有feasibility pump等等。

4，再说说怎么提高lower bound。第二点里说的当前分支的lower bound是local的，其实分支定界还有一个global的lower bound，即所有分支lower bound的最小值。

如果global的upper bound和lower bound无限接近，那么我们认为gap是0%，即我们已经找到optimal solution了。

那么提高这个global的lower bound的方法，有比如cutting plane，它可以提高LP线性规划的紧实度。

5，最后谈一下整数规划求解器，例如Cplex，Gurobi和Xpress。

这些求解器(算法包)已经为各位写好了复杂的分支定界和上面提到的启发式、割平面算法等等，而我们要做的，只是把一个整数规划模型用任何编程语言(例如C++、Matlab、Python等)输入进去，然后调用求解器即可求解。

求解器有一些参数可以设置，例如Time Limit，或者Optimality Gap等等。

另外如果你自己写了启发式算法得到了可行解，也可以作为初始解输入到求解器中。

以上这些请参考求解器的说明书。

最近这些求解器都支持多线程(小规模并行)计算，应该会是以后的研究热点。Cplex运算过程实例，https://stackoverflow.com/questions/30685125/mip-gap-couldnt-be-set-properly?rq=1

更多运筹学、整数规划干货：『运筹OR帷幄』大数据人工智能时代的运筹学​zhuanlan.zhihu.com