1. A Model-Oriented Approach for Lifting Symmetries in Answer Set Programming
- Author
-
Tarzariol, Alice
- Subjects
Computer Science - Logic in Computer Science ,Computer Science - Machine Learning - Abstract
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., Comment: In Proceedings ICLP 2022, arXiv:2208.02685. arXiv admin note: text overlap with arXiv:2112.11806
- Published
- 2022
- Full Text
- View/download PDF