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
Adaptive large-neighbourhood search for optimisation in answer-set programming
Institute for Logic and Computation, TU Wien, Favoritenstraße 9–11, Vienna, 1040, Austria.
Institute for Logic and Computation, TU Wien, Favoritenstraße 9–11, Vienna, 1040, Austria.
Institute for Logic and Computation, TU Wien, Favoritenstraße 9–11, Vienna, 1040, Austria.
Institute for Logic and Computation, TU Wien, Favoritenstraße 9–11, Vienna, 1040, Austria.
Show others and affiliations
2024 (English)In: Artificial Intelligence, ISSN 0004-3702, E-ISSN 1872-7921, Vol. 337, article id 104230Article in journal (Refereed) 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.

Place, publisher, year, edition, pages
Elsevier, 2024. Vol. 337, article id 104230
Keywords [en]
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
National Category
Computer and Information Sciences
Identifiers
URN: urn:nbn:se:hj:diva-66309DOI: 10.1016/j.artint.2024.104230ISI: 001322435400001Scopus ID: 2-s2.0-85204583992Local ID: HOA;intsam;975157OAI: oai:DiVA.org:hj-66309DiVA, id: diva2:1901933
Funder
EU, Horizon 2020, 101034440Available from: 2024-09-30 Created: 2024-09-30 Last updated: 2024-10-14Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Oetsch, Johannes

Search in DiVA

By author/editor
Oetsch, Johannes
By organisation
JTH, Department of Computing
In the same journal
Artificial Intelligence
Computer and Information Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 22 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