[Back]


Contributions to Proceedings:

T. Eiter, T. Geibinger, N. N. Higuera Ruiz, N. Musliu, J. Oetsch, D. Stepanova:
"Large-Neighbourhood Search for Optimisation in Answer-Set Solving";
in: "36th AAAI Conference on Artificial Intelligence (AAAI-22)", AAAI Press, 2022, 10 pages.



English abstract:
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.

German abstract:
Während die Answer-Set-Programmierung (ASP) ein prominenter Ansatz zur deklarativen Problemlösung ist, können Optimierungsprobleme immer noch eine Herausforderung für sie sein. Large Neighbourhood Search (LNS) ist eine Metaheuristik zur Optimierung, bei der Teile einer Lösung abwechselnd zerstört und rekonstruiert werden, die ein hohes, aber ungenutztes Potenzial für die ASP-Lösung hat. Wir stellen ein Framework für die LNS-Optimierung beim Lösen von Antwortmengen vor, in dem Nachbarschaften entweder deklarativ als Teil der ASP-Codierung angegeben oder automatisch durch Code generiert werden können. Um verschiedene Nachbarschaften effektiv zu erkunden, konzentrieren wir uns auf das Multi-Shot-Solving, da es ermöglicht, Programm-Regrounding zu vermeiden. Wir veranschaulichen den Rahmen für verschiedene Optimierungsprobleme, von denen einige notorisch schwierig sind, darunter Schichtplanung und ein paralleles Maschinenplanungsproblem aus der Halbleiterproduktion, die die Wirksamkeit des LNS-Ansatzes demonstrieren.

Keywords:
Large Neighborhood Search, Answer Set Programming

Created from the Publication Database of the Vienna University of Technology.