MILP加速运算技巧——模型预处理presolve

预处理是许多MIP求解器在正是求解前会进行的一个步骤，通过一些简单的策略来节省最终模型整体求解的规模，以提高模型的求解效率。

例如，Gurobi 求解器在求解过程之前会先对模型的约束和变量进行预处理，以下面的整数规划为例：

$$\begin{array}{rl}\min & ?2x?y\\ & \\ & 3x?5y\le 0\\ & \\ & 3x+5y\le 15\\ & \\ & x\ge 0,y\ge 0\\ & \\ & x,y\in Z\end{array}$$

import gurobipy as grb

# 建立框架
model = grb.Model()

# 定义整数变量
x = model.addVar(vtype=grb.GRB.INTEGER, name='x')
y = model.addVar(vtype=grb.GRB.INTEGER, name='y')

# 添加约束
model.addConstr(3 * x - 5 * y <= 0)
model.addConstr(3 * x + 5 * y <= 15)
model.addConstr(x >= 0)
model.addConstr(y >= 0)

# 定义目标函数
model.setObjective(-2 * x - y, sense=grb.GRB.MINIMIZE)

# 求解
model.optimize()

# 读取信息
print("目标函数值：", model.objVal)
for v in model.getVars():
    print('参数', v.VarName, '=', v.x)

在返回的求解日志当中，可以看到 Gurobi 对模型的预求解中缩减的约束及变量，日志内容如下：

...
Presolve removed 2 rows and 0 columns
Presolve time: 0.00s
Presolved: 2 rows, 2 columns, 4 nonzeros
Variable types: 0 continuous, 2 integer (0 binary)
...

有一些预处理的简单策略，能够通过极低的计算开销，带来整体模型求解效率的提升（尽管在一些特殊情况下，这些预处理策略不一定有效），这些策略包括：

1. 消除冗余约束：在一些模型当中会出现作用重叠的情况，例如，$x\ge 0$，与 $x+y\ge 3,x?y\ge 4$ 的作用域就有重叠的地方，前者就可以删除；
2. 增强变量边界（tighten formulation）：探寻约束或者变量更紧凑的边界，这个边界加强过程有可能会需要比较长的时间。例如第1点消除冗余约束的例子，通过后两个约束得到$x\ge 3.5$ 也是求得了变量 $x$ 的更紧凑边界；又比如，$x+y\ge 5,x\le 2,y\le 3$，此时得到 $x+y\le 5$，只能是 $x=2，y=3$ 的情况；又比如文章开始举的例子当中，通过约束1，2知道 $0\le x\le 2.5$，根据约束1又可知 $y\ge 1.5$；
3. 减小约束系数：如前面两种方法缩减，要消除冗余，增强边界等，都需要比较清晰系数关系，此时常常会先尽可能地将约束系数缩减，例如：$x1\ge 0，x2\ge 0$，且都为整数，若有约束 $2x1+2x3\le 1$，此时可以缩减约束系数为 $x1+x2\le 0.5$，综合考虑后发现， 只存在$x1=x2=0$的情况，即减小约束系数通常可以减少分支裁剪树当中的节点数（但并非总是如此，有时可能反而会增加节点上Relaxed-LP 的求解时间，当这些时间足以抵消节点数减少带来的优势的话，则预处理策略无益，这一个例子有点像高莫雷割平面），这类策略在整数规划当中大量使用，减少了节点数即减少了需要求解的Relaxed-LP 数，且不影响原本的MIP问题的可行解集合。