论文标题
有效提起对称性的限制，以解决复杂的组合问题
Efficient lifting of symmetry breaking constraints for complex combinatorial problems
论文作者
论文摘要
许多工业应用都需要找到具有挑战性的组合问题的解决方案。有效消除对称解决方案候选者是高性能解决方案的关键推动因素之一。但是，现有的基于模型的对称性破坏方法仅限于一组代表性和易于解决的实例的问题，在实际应用中通常不是这种情况。这项工作扩展了学习框架和基于模型的方法进行答案设置编程的方法，以克服这些限制并解决挑战性问题，例如合作伙伴单位问题。特别是，我们将一种新的冲突分析算法纳入了归纳逻辑编程系统ILASP，重新定义学习任务，并提出了一种新的示例生成方法来扩展方法。针对不同类型的伙伴单位问题实例进行的实验证明了我们方法的适用性以及由于所学到的一阶约束而引起的计算益处。
Many industrial applications require finding solutions to challenging combinatorial problems. Efficient elimination of symmetric solution candidates is one of the key enablers for high-performance solving. However, existing model-based approaches for symmetry breaking are limited to problems for which a set of representative and easily-solvable instances is available, which is often not the case in practical applications. This work extends the learning framework and implementation of a model-based approach for Answer Set Programming to overcome these limitations and address challenging problems, such as the Partner Units Problem. In particular, we incorporate a new conflict analysis algorithm in the Inductive Logic Programming system ILASP, redefine the learning task, and suggest a new example generation method to scale up the approach. The experiments conducted for different kinds of Partner Units Problem instances demonstrate the applicability of our approach and the computational benefits due to the first-order constraints learned.
