Skip to content

Research at St Andrews

A framework for constraint based local search using ESSENCE

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

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.
Close

Details

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
CountrySweden
CityStockholm
Period13/07/1819/07/18
Internet address

Discover related content
Find related publications, people, projects and more using interactive charts.

View graph of relations

Related by author

  1. Automatic discovery and exploitation of promising subproblems for tabulation

    Akgun, O., Gent, I. P., Jefferson, C. A., Miguel, I. J., Nightingale, P. W. & Salamon, A. Z., 2018, Principles and Practice of Constraint Programming: 24th International Conference, CP 2018, Lille, France, August 27-31, 2018, Proceedings. Hooker, J. (ed.). Springer, p. 3-12 (Lecture Notes in Computer Science; vol. 11008).

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

  2. Metamorphic testing of constraint solvers

    Akgun, O., Gent, I. P., Jefferson, C. A., Miguel, I. J. & Nightingale, P. W., 2018, Principles and Practice of Constraint Programming: 24th International Conference, CP 2018, Lille, France, August 27-31, 2018, Proceedings. Hooker, J. (ed.). Springer, p. 727-736 (Lecture Notes in Computer Science; vol. 11008).

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

  3. Automatically improving constraint models in Savile Row

    Nightingale, P., Akgün, Ö., Gent, I. P., Jefferson, C., Miguel, I. & Spracklen, P., Oct 2017, In : Artificial Intelligence. 251, p. 35-61 27 p.

    Research output: Contribution to journalArticle

  4. Exploiting short supports for improved encoding of arbitrary constraints into SAT

    Akgün, Ö., Gent, I. P., Jefferson, C. A., Miguel, I. J. & Nightingale, P. W., 2016, Principles and Practice of Constraint Programming: 22nd International Conference, CP 2016, Toulouse, France, September 5-9, 2016, Proceedings. Rueher, M. (ed.). Springer, p. 3-12 (Lecture Notes in Computer Science; vol. 9892).

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

  5. Automatically improving constraint models in Savile Row through associative-commutative common subexpression elimination

    Nightingale, P., Akgun, O., Gent, I. P., Jefferson, C. & Miguel, I., 8 Sep 2014, Principles and Practice of Constraint Programming. O'Sullivan, B. (ed.). Cham: Springer, p. 590-605 16 p. (Lecture Notes in Computer Science; vol. 8656).

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

ID: 253026207