Publikation: Lifting symmetry breaking constraints w...
Stammdaten
Titel: | Lifting symmetry breaking constraints with inductive logic programming |
Untertitel: | |
Kurzfassung: | 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. |
Schlagworte: | Artificial Intelligence, Software |
Publikationstyp: | Beitrag in Zeitschrift (Autorenschaft) |
Erscheinungsdatum: | 19.04.2022 (Online) |
Erschienen in: |
Machine Learning
Machine Learning
(
Springer;
)
zur Publikation |
Titel der Serie: | - |
Bandnummer: | 111 |
Heftnummer: | 4 |
Erstveröffentlichung: | Ja |
Version: | - |
Seite: | S. 1303 - 1326 |
Versionen
Keine Version vorhanden |
Erscheinungsdatum: | 04.2022 |
ISBN: | - |
ISSN: | 0885-6125 |
Homepage: | - |
Erscheinungsdatum: | 19.04.2022 |
ISBN (e-book): | - |
eISSN: | 1573-0565 |
DOI: | http://dx.doi.org/10.1007/s10994-022-06146-3 |
Homepage: | - |
Open Access |
|
Zuordnung
Organisation | Adresse | ||||
---|---|---|---|---|---|
Fakultät für Technische Wissenschaften
Institut für Artificial Intelligence und Cybersecurity
|
AT - A-9020 Klagenfurt |
Kategorisierung
Sachgebiete | |
Forschungscluster | Kein Forschungscluster ausgewählt |
Zitationsindex |
Informationen zum Zitationsindex: Master Journal List
|
Peer Reviewed |
|
Publikationsfokus |
Klassifikationsraster der zugeordneten Organisationseinheiten:
|
Arbeitsgruppen |
|
Kooperationen
Forschungsaktivitäten
(Achtung: Externe Aktivitäten werden im Suchergebnis nicht mitangezeigt)
Projekte: | Keine verknüpften Projekte vorhanden |
Publikationen: | Keine verknüpften Publikationen vorhanden |
Veranstaltungen: | Keine verknüpften Veranstaltung vorhanden |
Vorträge: |
|