郑州做网站加密的公司,资讯网站模板带会员投稿功能,南通企业网站制作,北京网站建设搜q.479185700文章目录 整数规划的对称性什么是对称性对称性的影响 对称性的预处理方法 整数规划的对称性
什么是对称性
许多整数规划问题存在对称性#xff0c;这种对称性是指问题解空间的对称#xff0c;即在对称的解空间当中解的优化目标值上是相同的。这种对称性并不会改变问题的最优… 文章目录 整数规划的对称性什么是对称性对称性的影响 对称性的预处理方法 整数规划的对称性
什么是对称性
许多整数规划问题存在对称性这种对称性是指问题解空间的对称即在对称的解空间当中解的优化目标值上是相同的。这种对称性并不会改变问题的最优值如果我们能够限制这种对称性就能在不改变问题最优值的情况下缩减问题可行空间的规模因此很多MIP求解器会对模型的对称性做出检测并进行处理。
以生产排程问题为例加入存在一批加工工件每个工件基于它的产品类型有一个加工工艺若工件1和工件2的加工工艺相同此时对于最终的生产方案而言加工工件1和加工工件2的每个步骤的顺序进行调换并不会影响问题的目标值此时工件1和工件2相关的所有决策变量具有对称性。
又例如 2 x 1 2 x 2 x 3 ≤ 10 , x 1 ≤ 5 , x 2 ≤ 5 2x12x2x3\leq 10, x1\leq 5, x2\leq 5 2x12x2x3≤10,x1≤5,x2≤5目标函数是 3 x 1 3 x 2 x 3 3x13x2x3 3x13x2x3此时不论最终的结果如何 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, sensegrb.GRB.MINIMIZE)在求解日志当中上述问题的所有约束和变量都被预处理过程确定下来当 y y y 确定后 x 1 x 2 x1x2 x1x2 的值能确定且由于 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⊤x≤d⊤π(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 n2 n2只有 x 1 , x 2 x1,x2 x1,x2 两个等价变量时对称性割就为 x 1 2 x 2 ≤ x 2 2 x 1 x12x2\leq x22x1 x12x2≤x22x1移项得 x 2 ≤ x 1 x2\leq x1 x2≤x1。这种约束就使得原本等价的两个解只能有一个是满足该约束的缩减了问题的解空间加速了BB算法的收敛。但值得注意的是有大量等价变量不仅意味着对称性割的加速效果显著也意味着添加的对称性割的数量庞大减少了相同的节点但增加了节点处问题的求解难度在实际中仍需要进行一定的权衡。
