Large-Neighbourhood Search for Optimisation in Answer-Set Solving

Thomas Eiter, Tobias Geibinger, Nelson Higuera Ruiz, Nysret Musliu, Johannes Oetsch, Daria Stepanova

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.
BibTeX
@inproceedings{eiter2022large,
  author = {Thomas Eiter and Tobias Geibinger and Nelson Higuera Ruiz and Nysret Musliu and Johannes Oetsch and Daria Stepanova},
  title = {{Large-Neighbourhood Search for Optimisation in Answer-Set Solving}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i5.20502},
}

Loading related content...

Figure