Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Large-Neighbourhood Search for Optimisation in Answer-Set Solving
Institute for Logic and Computation, TU Wien, Vienna, Austria.
Institute for Logic and Computation, TU Wien, Vienna, Austria.
Institute for Logic and Computation, TU Wien, Vienna, Austria.
Institute for Logic and Computation, TU Wien, Vienna, Austria; CD-Lab Artis, TU Wien, Vienna, Austria .
Show 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
Available from: 2024-02-16 Created: 2024-02-16 Last updated: 2024-02-16Bibliographically approved

Open Access in DiVA

No full text in DiVA

Scopus

Authority records

Oetsch, Johannes

Search in DiVA

By author/editor
Oetsch, Johannes
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 10 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf