MILP加速运算技巧——模型预处理presolve【草稿】

预处理是许多MIP求解器在正是求解前会进行的一个步骤，能通过一些简单策略的较低开销，节省最终模型整体求解中不必要的计算，提高求解效率。

这些简单策略包括消除模型中冗余的约束、提升模型的紧凑性（tighten formulation）、缩减模型规模等。

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

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

上面问题的presolve是所谓的LP-presolve，因为它不依赖于整数约束。 一个依赖整数约束的presolve例子如下。假设x1和x2是非负整数变量，并且有约束：2x1+ 2x2≤ 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中大量采用的操作。