Large-Neighbourhood Search for Optimisation in Answer-Set Solving


  • Thomas Eiter TU Wien
  • Tobias Geibinger TU Wien
  • Nelson Higuera Ruiz TU Wien
  • Nysret Musliu TU Wien
  • Johannes Oetsch TU Wien
  • Daria Stepanova Bosch Center for Artificial Intelligence



Knowledge Representation And Reasoning (KRR), Constraint Satisfaction And Optimization (CSO), Search And Optimization (SO), Planning, Routing, And Scheduling (PRS)


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.




How to Cite

Eiter, T., Geibinger, T., Higuera Ruiz, N., Musliu, N., Oetsch, J., & Stepanova, D. (2022). Large-Neighbourhood Search for Optimisation in Answer-Set Solving. Proceedings of the AAAI Conference on Artificial Intelligence, 36(5), 5616-5625.



AAAI Technical Track on Knowledge Representation and Reasoning