A Model-Oriented Approach for Lifting Symmetries in Answer Set Programming
This addresses a bottleneck in Answer Set Programming for researchers and practitioners dealing with combinatorial optimization, though it appears incremental as it builds on existing SBC methods.
The paper tackles the problem of efficiently pruning symmetric solutions in combinatorial problems by introducing a model-oriented approach that lifts Symmetry Breaking Constraints (SBCs) from small instances into interpretable first-order constraints using Inductive Logic Programming, aiming to avoid time-consuming recomputation for large-scale instances.
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.