Large-Neighbourhood Search for ASP OptimisationShow others and affiliations
2022 (English)In: Electronic Proceedings in Theoretical Computer Science, EPTCS, Open Publishing Association , 2022, p. 163-165Conference paper, Oral presentation with published abstract (Refereed)
Abstract [en]
While answer-set programming (ASP) is a successful approach to declarative problem solving optimisation can still be a challenge for it. Large-neighbourhood search (LNS) is a metaheuristic technique where parts of a solution are alternately destroyed and reconstructed, which has high but untapped potential for ASP solving. We present a framework for LNS optimisation for ASP, in which neighbourhoods can be specified either declaratively as part of the ASP encoding, or automatically generated by code. In the full paper, we illustrate the framework on different optimisation problems, some of which are notoriously difficult, including shift planning and a parallel machine scheduling problem from semi-conductor production which demonstrate the effectiveness of the LNS approach.
Place, publisher, year, edition, pages
Open Publishing Association , 2022. p. 163-165
Keywords [en]
Computer circuits, Logic programming, Answer set programming, Automatically generated, Declarative problem solving, Encodings, Large neighbourhood searches, Meta-heuristic techniques, Neighbourhood, Optimisations, Optimization problems, Search optimization, Optimization
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:hj:diva-63557DOI: 10.4204/EPTCS.364.23Scopus ID: 2-s2.0-85137578779OAI: oai:DiVA.org:hj-63557DiVA, id: diva2:1838547
Conference
38th International Conference on Logic Programming, ICLP 2022, 31 July-6 August 2022, Haifa, Israel
2024-02-162024-02-162024-02-16Bibliographically approved