Publikation: Learning to Break Symmetries for Effici...
Stammdaten
Titel: | Learning to Break Symmetries for Efficient Optimization in Answer Set Programming |
Untertitel: | |
Kurzfassung: | The ability to efficiently solve hard combinatorial optimization problems is a key prerequisite to various applications of declarative programming paradigms. Symmetries in solution candidates pose a significant challenge to modern optimization algorithms since the enumeration of such candidates might substantially reduce their performance. This paper proposes a novel approach using Inductive Logic Programming (ILP) to lift symmetry-breaking constraints for optimization problems modeled in Answer Set Programming (ASP). Given an ASP encoding with optimization statements and a set of small representative instances, our method augments ground ASP programs with auxiliary normal rules enabling the identification of symmetries using existing tools, like SBASS. Then, the obtained symmetries are lifted to first-order constraints with ILP. We prove the correctness of our method and evaluate it on real-world optimization problems from the domain of automated configuration. Our experiments show significant improvements of optimization performance due to the learned first-order constraints. |
Schlagworte: | Psychiatry and Mental health, Neuropsychology and Physiological Psychology |
Publikationstyp: | Beitrag in Proceedings (Autorenschaft) |
Erscheinungsdatum: | 26.06.2023 (Online) |
Erschienen in: |
Proceedings of the 37th AAAI Conference on Artificial Intelligence
Proceedings of the 37th AAAI Conference on Artificial Intelligence
(
AAAI Press;
B. Williams, Y. Chen, J. Neville
)
zur Publikation |
Titel der Serie: | - |
Bandnummer: | 37 |
Erstveröffentlichung: | Ja |
Version: | - |
Seite: | S. 6541 - 6549 |
Versionen
Keine Version vorhanden |
Erscheinungsdatum: | 26.06.2023 |
ISBN (e-book): | - |
eISSN: | 2374-3468 |
DOI: | http://dx.doi.org/10.1609/aaai.v37i5.25804 |
Homepage: | - |
Open Access |
|
AutorInnen
Alice Tarzariol (intern) |
Martin Gebser (intern) |
Konstantin Schekotihin (intern) |
Mark Law (extern) |
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 |
Peer Reviewed |
|
Publikationsfokus |
Klassifikationsraster der zugeordneten Organisationseinheiten:
|
Arbeitsgruppen |
|
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: |
|