论文标题
在二进制程序中处理循环对称性的有效繁殖技术
Efficient Propagation Techniques for Handling Cyclic Symmetries in Binary Programs
论文作者
论文摘要
二进制程序的对称性的存在通常会降低分支结合求解器的性能。在本文中，我们得出有效的可变固定算法，以基于循环基团的传播技术从搜索空间中丢弃对称解。我们的算法伴随着可以找到可以从对称参数派生的所有可能变量固定的保证，即，一个人找不到比我们算法所发现的更可变的固定因素。由于二进制程序的每个置换对称组都有环状亚组，因此衍生算法可用于处理任何对称二进制程序中的对称性。在实验中，我们还提供了数值证据，表明我们的算法比其他变量固定算法更有效地处理对称性。
The presence of symmetries of binary programs typically degrade the performance of branch-and-bound solvers. In this article, we derive efficient variable fixing algorithms to discard symmetric solutions from the search space based on propagation techniques for cyclic groups. Our algorithms come with the guarantee to find all possible variable fixings that can be derived from symmetry arguments, i.e., one cannot find more variable fixings than those found by our algorithms. Since every permutation symmetry group of a binary program has cyclic subgroups, the derived algorithms can be used to handle symmetries in any symmetric binary program. In experiments we also provide numerical evidence that our algorithms handle symmetries more efficiently than other variable fixing algorithms for cyclic symmetries.
