Large-Neighbourhood Search for Optimisation in Answer-Set SolvingShow others and affiliations
2022 (English)In: Proceedings of the 36th AAAI Conference on Artificial Intelligence, AAAI 2022, Association for the Advancement of Artificial Intelligence , 2022, p. 5616-5625Conference paper, Published paper (Refereed)
Abstract [en]
While Answer-Set Programming (ASP) is a prominent approach to declarative problem solving, optimisation problems can still be a challenge for it. Large-Neighbourhood Search (LNS) is a metaheuristic for optimisation where parts of a solution are alternately destroyed and reconstructed that has high but untapped potential for ASP solving. We present a framework for LNS optimisation in answer-set solving in which neighbourhoods can be specified either declaratively as part of the ASP encoding or automatically generated by code. To effectively explore different neighbourhoods, we focus on multi-shot solving as it allows to avoid program regrounding. 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
Association for the Advancement of Artificial Intelligence , 2022. p. 5616-5625
Keywords [en]
Logic programming, Answer set programming, Answer Set Solving, Declarative problem solving, Encodings, Large neighbourhood searches, Metaheuristic, Neighbourhood, Optimisations, Optimization problems, Search optimization, Optimization
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:hj:diva-63558Scopus ID: 2-s2.0-85137595873ISBN: 1577358767 (print)ISBN: 9781577358763 (print)OAI: oai:DiVA.org:hj-63558DiVA, id: diva2:1838574
Conference
36th AAAI Conference on Artificial Intelligence, AAAI 2022, 22 February-1 March 2022
2024-02-162024-02-162024-02-16Bibliographically approved