A framework for constraint based local search using ESSENCE

Ozgur Akgun, Saad Wasim A Attieh, Ian Philip Gent, Christopher Anthony Jefferson, Ian James Miguel, Peter William Nightingale, András Z. Salamon, Patrick Spracklen, James Patrick Wetter

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Citations (Scopus)

Abstract

Structured Neighbourhood Search (SNS) is a framework for constraint-based local search for problems expressed in the Essence abstract constraint specification language. The local search explores a structured neighbourhood, where each state in the neighbourhood preserves a high level structural feature of the problem. SNS derives highly structured problem-specific neighbourhoods automatically and directly from the features of the ESSENCE specification of the problem. Hence, neighbourhoods can represent important structural features of the problem, such as partitions of sets, even if that structure is obscured in the low-level input format required by a constraint solver. SNS expresses each neighbourhood as a constrained optimisation problem, which is solved with a constraint solver. We have implemented SNS, together with automatic generation of neighbourhoods for high level structures, and report high quality results for several optimisation problems.
Original languageEnglish
Title of host publicationProceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
EditorsJérôme Lang
PublisherInternational Joint Conferences on Artificial Intelligence
Pages1242-1248
Number of pages7
ISBN (Electronic)9780999241127
DOIs
Publication statusPublished - 13 Jul 2018
Event27th International Joint Conference on Artificial Intelligence and the 23rd European Conference on Artificial Intelligence - Stockholmsmässan, Älvsjö , Stockholm, Sweden
Duration: 13 Jul 201819 Jul 2018
Conference number: 27/23
https://www.ijcai-18.org/

Conference

Conference27th International Joint Conference on Artificial Intelligence and the 23rd European Conference on Artificial Intelligence
Abbreviated titleIJCAI-ECAI-18
Country/TerritorySweden
CityStockholm
Period13/07/1819/07/18
Internet address

Keywords

  • Constraints and SAT: constraint satisfaction
  • Constraints and SAT: modeling; formulation
  • Constraints and SAT: constraint ptimisation
  • Constraints and SAT: Constraints: solvers and tools

Fingerprint

Dive into the research topics of 'A framework for constraint based local search using ESSENCE'. Together they form a unique fingerprint.

Cite this