Journal
MACHINE LEARNING
Volume 111, Issue 4, Pages 1303-1326Publisher
SPRINGER
DOI: 10.1007/s10994-022-06146-3
Keywords
Answer set programming; Inductive logic programming; Symmetry breaking constraints
Categories
Funding
- KWF Project [28472]
- cms electronics GmbH
- FunderMax GmbH
- Hirsch Armbander GmbH
- IT GmbH
- Infineon Technologies Austria AG
- Isovolta AG
- Kostwein Holding GmbH
- Privatstiftung Karntner Sparkasse
Ask authors/readers for more resources
Efficiently excluding symmetric solution candidates is crucial for combinatorial problem-solving. Existing approaches that compute Symmetry Breaking Constraints (SBCs) for specific problem instances may not be applicable to large-scale instances or advanced problem encodings. To overcome these limitations, we propose a model-oriented approach that transforms SBCs of small problem instances into interpretable first-order constraints using Inductive Logic Programming.
Efficient omission of symmetric solution candidates is essential for combinatorial problem-solving. 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 the Inductive Logic Programming paradigm. Experiments demonstrate the ability of our framework to learn general constraints from instance-specific SBCs for a collection of combinatorial problems. The obtained results indicate that our approach significantly outperforms a state-of-the-art instance-specific method as well as the direct application of a solver.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available