Öppna denna publikation i ny flik eller fönster >>Visa övriga...
2024 (Engelska)Ingår i: Artificial Intelligence, ISSN 0004-3702, E-ISSN 1872-7921, Vol. 337, artikel-id 104230Artikel i tidskrift (Refereegranskat) Published
Abstract [en]
Answer-set programming (ASP) is a prominent approach to declarative problem solving that is increasingly used to tackle challenging optimisation problems. We present an approach to leverage ASP optimisation by using large-neighbourhood search (LNS), which is a meta-heuristic where parts of a solution are iteratively destroyed and reconstructed in an attempt to improve an overall objective. In our LNS framework, neighbourhoods can be specified either declaratively as part of the ASP encoding or automatically generated by code. Furthermore, our framework is self-adaptive, i.e., it also incorporates portfolios for the LNS operators along with selection strategies to adjust search parameters on the fly. The implementation of our framework, the system ALASPO, currently supports the ASP solver clingo, as well as its extensions clingo-dl and clingcon that allow for difference and full integer constraints, respectively. It utilises multi-shot solving to efficiently realise the LNS loop and in this way avoids program regrounding. We describe our LNS framework for ASP as well as its implementation, discuss methodological aspects, and demonstrate the effectiveness of the adaptive LNS approach for ASP on different optimisation benchmarks, some of which are notoriously difficult, as well as real-world applications for shift planning, configuration of railway-safety systems, parallel machine scheduling, and test laboratory scheduling.
Ort, förlag, år, upplaga, sidor
Elsevier, 2024
Nyckelord
Integer programming, Railroad transportation, Adaptive large neighborhood searches, Answer set programming, Automatically generated, Declarative problem solving, Encodings, Large neighbourhood searches, Metaheuristic, Neighbourhood, Optimisations, Optimization problems, Benchmarking
Nationell ämneskategori
Data- och informationsvetenskap
Identifikatorer
urn:nbn:se:hj:diva-66309 (URN)10.1016/j.artint.2024.104230 (DOI)001322435400001 ()2-s2.0-85204583992 (Scopus ID)HOA;intsam;975157 (Lokalt ID)HOA;intsam;975157 (Arkivnummer)HOA;intsam;975157 (OAI)
Forskningsfinansiär
EU, Horisont 2020, 101034440
2024-09-302024-09-302024-10-14Bibliografiskt granskad