找出给定一系列整数中的最小值_优化｜用Branch-and-Cut 解混合整数规划

『运筹OR帷幄』转载

作者：魏晓阳

编者按

Branch-and-Cut 是求解整数规划或混合整数规划问题最常用的算法之一。通常，把全部可行解空间反复地分割为越来越小的子集，称为分支；并且对每个子集内的解集计算一个目标下界(对于最小值问题)，称为定界；在每次分枝后，凡是界限超出已知可行解集目标值的子集不再进一步考虑，称为剪枝。这就是Branch-and-Cut的主要思路。

一Gurobi求解的MIP问题形式

Gurobi MIP求解器，最常求解的问题形式是：

整数约束使MIP模型可以获得离散特征的决策。比如，某个值限制为0或1，即0-1约束，可以表示是否采取某个行为，比如决定vehicle是否通过某条路径。

Gurobi MIP求解器还可以求解具有二次目标和(或)二次约束的模型：

具有二次目标但没有二次约束的MIP模型称为混合整数二次规划(Mixed Integer Quadratic Programming, MIQP) 问题。具有二次约束的MIP模型称为混合整数二次约束规划(Mixed Integer Quadratically Constrained Programming, MIQCP)问题。没有任何二次特征的模型通常被称为混合整数线性规划(MILP)问题。以下是Gurobi用于解决MILP模型的算法的描述， MIQP和MIQCP与此类似。

二Branch-and-Bound

MILP问题一般用基于Branch-and-Bound算法的线性规划来解。

1. 总述

基本的基于LP的分支定界如下：

从最初的MIP开始，首先删除所有的整数约束，得到的LP称为原始MIP的线性规划松弛。我们解这个LP，如果结果恰好满足所有整数限制，太幸运了，该解决方案是原始MIP的最优解，运算终止；如果结果没有满足所有整数限制(大多数是这种情况)，需要选择某个整数约束、实际是小数值的变量进行branch。为了便于说明，假设这个变量是x，它在LP松弛中的值是5.7。然后，我们可以通过施加x≤5.0和x≥6.0的限制来排除该值5.7。

如果原始MIP问题用 P0 表示，那么用 P1 表示新的MIP(x≤5.0)，用 P2 表示新的MIP(x≥6.0)。变量x被称为分支变量，并且我们在x上已经进行了分支，产生了两个子MIP P1 和 P2 。很明显，如果我们可以计算 P1 和 P2 的最优解，那么较好的解就是原始问题 P0 的最优解。通过这种方式，我们用两个较简单(或更少整数限制)的MIP取代了 P0 。我们现在将相同的思想应用于这两个子MIP，并在必要时选择新的分支变量，这样生成所谓的搜索树。搜索过程生成的MIP称为树的节点， P0 为根节点，树的叶子是尚未branch的所有节点。如果我们可以解决或处置了所有叶节点，那么就求解了原始MIP问题。

Branch-and-Bound中的每个节点都是一个新的MIP

2. Fathomed and Incumbent 节点

为了更清楚地描述分支定界，说一下在处理搜索树节点时的逻辑。

首先，将搜索过程中当前最优解标记为incumbent，很明显，在最初搜索时，没有incumbent。

假设目标函数是最小化，并刚刚求解了搜索树中某个节点的LP松弛。如果在该节点的solution中满足原始MIP中的所有整数约束，那么就找到了原始MIP的可行解(注意不是最优解)。

然后会发生：

(1) 求解器将此节点标记为fathomed。表示没有必要在这个节点上继续进行分支，该节点成为了搜索树的永久叶子。

(2) 计算刚刚找到的feasible solution的函数值。如果我们刚刚发现的整数可行解具有比当前incumbent更好的目标函数值(或者当前没有incumbent)，那么将此feasible solution的目标函数值设为新的incumbent。否则，不需要更新incumbent，只需继续搜索。

将节点标记为fathomed的另外两种可能是：

(1) 该节点的branch产生的Relaxed-LP无解，则更不可能包含整数可行解。

(2) 该节点的branch产生的最优松弛解，其目标值大于当前incumbent，则不可能包含更优整数可行解。

3. Best Bound 和 Gap

为了更清楚地描述分支定界，介绍一下另外两个重要值。

首先，一旦我们有incumbent，假设最初的MIP是最小化问题，该incumbent是给定MIP的最优解的上限。也就是说，求解器永远不会接受高于此值的整数解。

另外，在分支定界搜索期间的任何时候，我们也有一个有效的下限，称为Best Bound。Best Bound是所有当前叶节点的最优目标值中的最小者。

最后，当前上限和下限之间的差值称为Gap。当Gap=0时，我们则证明了当前incumbent是最优的。

三Presolve,CuttingPlanes,

Heuristics, Parallelism

近年来，MIP运算能力取得显着进步的原因在于：Presolve、Cutting Planes、Heuristics、Parallelism。

1. Presolve (预处理)

Presolve是在分支定界程序开始之前的一系列操作，旨在减少问题规模和tighten formulation。

用一个例子来说明，假设给定的问题包含以下约束：

x1+ x2+ x3≥ 15

x1≤ 7

x2≤ 3

x3≤ 5

显然，满足所有这些约束的唯一方法是x1 = 7，x2 = 3，x3 = 5。因此，将x1 、x2 、x3 替换为 7、3、5，将上述四个约束从模型中删除。

上面问题的presolve是所谓的LP-presolve，因为它不依赖于整数约束。 一个依赖整数约束的presolve例子如下。假设x1和x2是非负整数变量，并且有约束：2*x1+ 2*x2≤ 1。

不等式两边同时除以2，得到：x1+ x2≤ ½。

由于x1和x2具体整数约束，因此明显x1+x2≤0，又x1、x2具有非负性，则x1 = x2 = 0。因此，这两个变量用具体数值替代，这个约束从模型中删除。

需要注意，这两种presolve在性质上不同。第1种presolve没有减少relaxed-LP解的集合，更不会减少原MIP可行解的集合；第2种presolve减少了relaxed-LP解的集合，但没有减小原MIP可行解的集合。第2种presolve对于整数规划求解加速至关重要，是MIP presolve中大量采用的操作。

2. Cutting Planes (割平面)

割平面通常认为是整数规划中提升计算效率的最重要技巧。

切割平面的思想是通过去除一些非整数解，就想MIP-based presolve一样，达到tighten formulation的目的。割平面不像branching，branching会产生两个子问题(两个分支)，cutting plane只是切掉一些边角(如下图)，不会产生2个MIP。

Cutting Planes

用一个简单例子来说明cutting plane。假设formulation包含下面的constraint：

6 x1+ 5 x2+ 7 x3+ 4 x4+ 5 x5≤ 15

从x1到x5为0-1变量。假设我们刚刚求解了LP松弛问题，并且这些变量在该LP松弛中的值：x1 = 0，x2 = 1，x3 = x4 = x5 = 3/4。由于7 + 4 + 5 = 16> 15，因此x3 = x4 = x5 = 1是不可能的，因此以下新的不等式是原MIP的有效补充：

x3 + x4 + x5≤2

由于3/4 + 3/4 + 3/4 = 9/4> 2，新的不等式会切除当前的非整数最优解。这个inequality叫做knapsack cover。

一个重要问题：为什么没有在求解开始时添加这个新约束或cut(即静态添加)？

原因如下：

(i) 一般存在大量这样的约束，找到所有约束的时间成本非常高，而且可能无法将它们全部添加到模型中(内存原因)。

(ii) 增加约束可能使得LP松弛难以求解。

所以，只有当我们知道某些约束会有帮助时，才会添加这些约束。这叫动态添加。

3. Heuristics (启发式)

回想一下，我们上面提到的incumbent概念。尽快找到好的incumbent，对快速求解MIP有非常重要的意义：incumbent的值越高，LP松弛的值越可能超过它(在最小化问题中)，从而决定该节点不需要进一步branch(或者说cut掉)。

现在我们知道，在搜索树的某些节点上做一些额外的工作(heuristics)以找到更好的incumbent非常有价值的。找的方法是：当前可能许多整数变量不是整数，但其值非常接近整数，将一些变量舍入到它们附近的整数值，将它们固定到这些值，解决所产生的LP松弛，并重复这个过程几次，希望所有整数约束都被满足。

如果新产生的feasible solution具有比当前incumbent更好的目标值，则将新feasible soluton 值取代当前incumbent并继续进行。Gurobi包含多种不同的启发式算法，这是目前优于CPLEX的一个地方。

4. Parallelism (并行计算)

并行运算的基础是：MIP树搜索中的不同节点可以独立处理。很明显，根节点几乎无法进行并行计算。因此，需要搜索large tree的模型可以非常有效地利用多核处理器，而在根节点上花费大部分运行时间的模型在利用多核方面非常受限。

Parallel Branch and Bound

四其他

除了上面讨论的这些加速技巧，MIP求解器还(将会)应用其他一些求解技巧。包括：选择哪个variable进行branch、node presolve、对称性检测、互斥subtree的检测。目标是尽可能减小必须搜索的branch-and-bound tree的规模。

这里讨论的加速技巧可以通过Gurobi参数进行调整。Gurobi Optimizer的默认参数是尽可能适用于各种模型，虽然某些模型可以从调参中额外受益。这就涉及到了令一个话题：Gurobi如何调参。

参考文献：

http://www.gurobi.com/resources/getting-started/mip-basics