论文标题
一种以模型为导向的方法，用于在答案集编程中提起对称性
A Model-Oriented Approach for Lifting Symmetries in Answer Set Programming
论文作者
论文摘要
在解决组合问题时，必须从搜索空间中修剪对称解决方案候选者。大多数现有方法是特定于实例的，并专注于每个给定的问题实例的对称破坏约束（SBC）的自动计算。但是，由于计算出的SBC是命题，因此将这种方法应用于大规模实例或高级问题编码可能是有问题的，因此既不能被有意义地解释或转移到其他实例中。结果，必须在求解器的每次调用之前进行耗时的SBC重新计算。 为了克服这些局限性，我们引入了一种新的面向模型的方法，用于答案集编程，该方法将小问题实例的SBC提升为一组可解释的一阶约束，使用一种称为归纳逻辑编程的机器学习形式。在针对简单的组合问题之后，我们旨在扩展我们的方法，也可以应用于高级决策和优化问题。
When solving combinatorial problems, pruning symmetric solution candidates from the search space is essential. Most of the existing approaches are instance-specific and focus on the automatic computation of Symmetry Breaking Constraints (SBCs) for each given problem instance. However, the application of such approaches to large-scale instances or advanced problem encodings might be problematic since the computed SBCs are propositional and, therefore, can neither be meaningfully interpreted nor transferred to other instances. As a result, a time-consuming recomputation of SBCs must be done before every invocation of a solver. To overcome these limitations, we introduce a new model-oriented approach for Answer Set Programming that lifts the SBCs of small problem instances into a set of interpretable first-order constraints using a form of machine learning called Inductive Logic Programming. After targeting simple combinatorial problems, we aim to extend our method to be applied also for advanced decision and optimization problems.
