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

Standard

A framework for constraint based local search using ESSENCE. / Akgun, Ozgur; Attieh, Saad Wasim A; Gent, Ian Philip; Jefferson, Christopher Anthony; Miguel, Ian James; Nightingale, Peter William; Salamon, András Z.; Spracklen, Patrick; Wetter, James Patrick.

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence. ed. / Jérôme Lang. International Joint Conferences on Artificial Intelligence, 2018. p. 1242-1248.

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

Harvard

Akgun, O, Attieh, SWA, Gent, IP, Jefferson, CA, Miguel, IJ, Nightingale, PW, Salamon, AZ, Spracklen, P & Wetter, JP 2018, A framework for constraint based local search using ESSENCE. in J Lang (ed.), Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence. International Joint Conferences on Artificial Intelligence, pp. 1242-1248, 27th International Joint Conference on Artificial Intelligence and the 23rd European Conference on Artificial Intelligence, Stockholm, Sweden, 13/07/18. https://doi.org/10.24963/ijcai.2018/173

APA

Akgun, O., Attieh, S. W. A., Gent, I. P., Jefferson, C. A., Miguel, I. J., Nightingale, P. W., ... Wetter, J. P. (2018). A framework for constraint based local search using ESSENCE. In J. Lang (Ed.), Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (pp. 1242-1248). International Joint Conferences on Artificial Intelligence. https://doi.org/10.24963/ijcai.2018/173

Vancouver

Akgun O, Attieh SWA, Gent IP, Jefferson CA, Miguel IJ, Nightingale PW et al. A framework for constraint based local search using ESSENCE. In Lang J, editor, Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence. International Joint Conferences on Artificial Intelligence. 2018. p. 1242-1248 https://doi.org/10.24963/ijcai.2018/173

Author

Akgun, Ozgur ; Attieh, Saad Wasim A ; Gent, Ian Philip ; Jefferson, Christopher Anthony ; Miguel, Ian James ; Nightingale, Peter William ; Salamon, András Z. ; Spracklen, Patrick ; Wetter, James Patrick. / A framework for constraint based local search using ESSENCE. Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence. editor / Jérôme Lang. International Joint Conferences on Artificial Intelligence, 2018. pp. 1242-1248

Bibtex - Download

@inproceedings{413b9d1324cf4826b5ea1a130eb96159,
title = "A framework for constraint based local search using ESSENCE",
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.",
author = "Ozgur Akgun and Attieh, {Saad Wasim A} and Gent, {Ian Philip} and Jefferson, {Christopher Anthony} and Miguel, {Ian James} and Nightingale, {Peter William} and Salamon, {Andr{\'a}s Z.} and Patrick Spracklen and Wetter, {James Patrick}",
note = "Funding: UK Engineering & Physical Sciences Research Council (EPSRC) grants EP/P015638/1and EP/P026842/1.",
year = "2018",
month = "7",
day = "13",
doi = "10.24963/ijcai.2018/173",
language = "English",
pages = "1242--1248",
editor = "J{\'e}r{\^o}me Lang",
booktitle = "Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence",
publisher = "International Joint Conferences on Artificial Intelligence",

}

RIS (suitable for import to EndNote) - Download

TY - GEN

T1 - A framework for constraint based local search using ESSENCE

AU - Akgun, Ozgur

AU - Attieh, Saad Wasim A

AU - Gent, Ian Philip

AU - Jefferson, Christopher Anthony

AU - Miguel, Ian James

AU - Nightingale, Peter William

AU - Salamon, András Z.

AU - Spracklen, Patrick

AU - Wetter, James Patrick

N1 - Funding: UK Engineering & Physical Sciences Research Council (EPSRC) grants EP/P015638/1and EP/P026842/1.

PY - 2018/7/13

Y1 - 2018/7/13

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

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

U2 - 10.24963/ijcai.2018/173

DO - 10.24963/ijcai.2018/173

M3 - Conference contribution

SP - 1242

EP - 1248

BT - Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence

A2 - Lang, Jérôme

PB - International Joint Conferences on Artificial Intelligence

ER -

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