MILP加速运算技巧——模型对称性的预处理

---

整数规划的对称性

什么是对称性

许多整数规划问题存在对称性，这种对称性是指问题解空间的对称，即在对称的解空间当中解的优化目标值上是相同的。这种对称性并不会改变问题的最优值，如果我们能够限制这种对称性，就能在不改变问题最优值的情况下，缩减问题可行空间的规模，因此很多MIP求解器会对模型的对称性做出检测并进行处理。

以生产排程问题为例，加入存在一批加工工件，每个工件基于它的产品类型有一个加工工艺，若工件1和工件2的加工工艺相同，此时，对于最终的生产方案而言，加工工件1和加工工件2的每个步骤的顺序进行调换，并不会影响问题的目标值，此时工件1和工件2相关的所有决策变量具有对称性。

又例如：$2x1+2x2+x3\le 10,x1\le 5,x2\le 5$，目标函数是 $3x1+3x2+x3$，此时不论最终的结果如何，$x1,x2$之间的解进行调换，都不会影响目标值，原因是 $x1,x2$ 不论是约束系数，还是边界，以及目标函数系数都相同，他们的最优解互相对调，也是一个最优解，两个变量具有对称性。

例如以Gurobi预处理为例：

# 添加约束
model.addConstr(2*x1+ 2*x2 + y <= 10)
model.addConstr(x1 <= 5)
model.addConstr(x2 <= 5)
model.addConstr(y >= 5)
# 定义目标函数
model.setObjective(3*x1 +3*x2 + y, sense=grb.GRB.MINIMIZE)

在求解日志当中，上述问题的所有约束和变量都被预处理过程确定下来，当 $y$ 确定后，$x1+x2$ 的值能确定，且由于 $x1,x2$ 两个变量对称，所以问题的最优解不唯一。

...
Presolve removed 4 rows and 3 columns
Presolve time: 0.00s
Presolve: All rows and columns removed
...

许多的整数规划问题当中都存在这样的特点，例如在车辆路径问题当中，有两个点到其他所有点的距离都一样，此时这两个点不论先通过哪个点都是一样的，但在求解问题当中，其中一个点在前的方案、以及另一个点在前的方案都包含在问题的可行域内，尽管两者是等价的。

对称性的影响

很显然，过于强烈的对称性有时候就会产生无效的搜索动作。特别是对于经典的精确搜索框架——分支定界，对称的变量会导致大量重复的待搜索节点（子问题），不论是界的收敛还是待剪支数量，对称性都会在这个过程中造成大量的无效动作。而这种具有对称性的等价变量越多，则问题当中等价的可行解就越多，相同节点也就越多，算法的搜索就会变慢。

对于一些问题而言，因为对称性导致原本不复杂的问题，往往难以直接通过求解器在可接受的时间内得到满意的解，因此对于这个混合整数变量的问题，需要采取一定的办法进行处理。

对称性的预处理方法

前面提到，这种等价变量的一个特点就是约束系数以及目标函数系数都一致，因此需要打破这种对称性，而这只需要改变系数的一致性即可，对于一些问题而言，这个动作能直接将求解问题的时间缩短几十上千倍。

一些求解器会建立具有任意目标函数系数的模型，而更一般性的方法是增加对称性割，即添加破坏这种对称性的约束条件：既然这些变量是等价变量，那就增加约束来使得这些变量的值不等价，有一个倾向性，减少算法搜索另一些等价的对称解空间，以此来提升算法效率，这对于大规模的且有大量等价变量的问题尤为重要。

对称性割的基本形式为：

$d^{\top }x\le d^{\top }\pi (x)$

其中，$\pi$是置换算子，$d=(2^{n-1},2^{x-2},...2^0)$，$n$ 是具有对称性的等价变量数量。例如当 $n=2$，只有 $x1,x2$ 两个等价变量时，对称性割就为 $x1+2x2\le x2+2x1$，移项得 $x2\le x1$。这种约束就使得原本等价的两个解，只能有一个是满足该约束的，缩减了问题的解空间，加速了B&B算法的收敛。但值得注意的是，有大量等价变量不仅意味着对称性割的加速效果显著，也意味着添加的对称性割的数量庞大，减少了相同的节点，但增加了节点处问题的求解难度，在实际中仍需要进行一定的权衡。