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

2023-12-17 23:41:37


整数规划的对称性

什么是对称性

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

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

又例如: 2 x 1 + 2 x 2 + x 3 ≤ 10 , x 1 ≤ 5 , x 2 ≤ 5 2x1+2x2+x3\leq 10, x1\leq 5, x2\leq 5 2x1+2x2+x310,x15,x25,目标函数是 3 x 1 + 3 x 2 + x 3 3x1+3x2+x3 3x1+3x2+x3,此时不论最终的结果如何, x 1 , x 2 x1,x2 x1,x2之间的解进行调换,都不会影响目标值,原因是 x 1 , x 2 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 y y 确定后, x 1 + x 2 x1+x2 x1+x2 的值能确定,且由于 x 1 , x 2 x1,x2 x1,x2 两个变量对称,所以问题的最优解不唯一。

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

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

对称性的影响

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

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

对称性的预处理方法

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

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

对称性割的基本形式为:

d ? x ≤ d ? π ( x ) d^{\top}x \leq d^{\top}\pi (x) d?xd?π(x)

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

文章来源:https://blog.csdn.net/Linshaodan520/article/details/134947213
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。