Exploiting partial knowledge in declarative domain-specific heuristics for ASP

No Thumbnail Available
Access rights
openAccess
Journal Title
Journal ISSN
Volume Title
Conference article
This publication is imported from Aalto University research portal.
View publication in the Research portal

Other link related to publication
Date
2019-09-19
Major/Subject
Mcode
Degree programme
Language
en
Pages
14
22-35
Series
Electronic Proceedings in Theoretical Computer Science, EPTCS, Volume 306
Abstract
Domain-specific heuristics are an important technique for solving combinatorial problems efficiently. We propose a novel semantics for declarative specifications of domain-specific heuristics in Answer Set Programming (ASP). Decision procedures that are based on a partial solution are a frequent ingredient of existing domain-specific heuristics, e.g., for placing an item that has not been placed yet in bin packing. Therefore, in our novel semantics negation as failure and aggregates in heuristic conditions are evaluated on a partial solver state. State-of-the-art solvers do not allow such a declarative specification. Our implementation in the lazy-grounding ASP system Alpha supports heuristic directives under this semantics. By that, we also provide the first implementation for incorporating declaratively specified domain-specific heuristics in a lazy-grounding setting. Experiments confirm that the combination of ASP solving with lazy grounding and our novel heuristics can be a vital ingredient for solving industrial-size problems.
Description
| openaire: EC/H2020/825619/EU//AI4EU
Keywords
Other note
Citation
Taupe , R , Schekotihin , K , Schüller , P , Weinzierl , A & Friedrich , G 2019 , ' Exploiting partial knowledge in declarative domain-specific heuristics for ASP ' , Electronic Proceedings in Theoretical Computer Science, EPTCS , vol. 306 , pp. 22-35 . https://doi.org/10.4204/EPTCS.306.9