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

doi:10.24963/ijcai.2018/173

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 proceeding › Conference 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.

Original language	English
Title of host publication	Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Editors	Jérôme Lang
Publisher	International Joint Conferences on Artificial Intelligence
Pages	1242-1248
Number of pages	7
ISBN (Electronic)	9780999241127
DOIs	https://doi.org/10.24963/ijcai.2018/173
Publication status	Published - 13 Jul 2018
Event	27th International Joint Conference on Artificial Intelligence and the 23rd European Conference on Artificial Intelligence - Stockholmsmässan, Älvsjö , Stockholm, Sweden Duration: 13 Jul 2018 → 19 Jul 2018 Conference number: 27/23 https://www.ijcai-18.org/

Conference

Conference	27th International Joint Conference on Artificial Intelligence and the 23rd European Conference on Artificial Intelligence
Abbreviated title	IJCAI-ECAI-18
Country/Territory	Sweden
City	Stockholm
Period	13/07/18 → 19/07/18
Internet address	https://www.ijcai-18.org/

Keywords

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

Access to Document

10.24963/ijcai.2018/173

Akgun-2018-A-framework-IJCAI-0173
Copyright © 2018, IJCAI. This work has been made available online in accordance with the publisher’s policies. This is the final published version of the work, which was originally published at https://doi.org/10.24963/ijcai.2018/173
Final published version, 124 KB

Modelling and Optimisation with Graphs: Modelling and Optimisation with Graphs
Jefferson, C. A. (PI) & Akgun, O. (CoI)
EPSRC
1/07/17 → 31/10/20
Project: Standard

Ozgur Akgun
- ozgur.akgunst-andrews.acuk
- School of Computer Science - Senior Lecturer, Director of Impact
- Centre for Interdisciplinary Research in Computational Algebra
Person: Academic
Christopher Anthony Jefferson
- caj21st-andrews.acuk
Person: Academic

Cite this

Akgun, O., Attieh, S. W. A., Gent, I. P., Jefferson, C. A., Miguel, I. J., Nightingale, P. W., Salamon, A. Z., Spracklen, P., & 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

@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.",

keywords = "Constraints and SAT: constraint satisfaction, Constraints and SAT: modeling; formulation, Constraints and SAT: constraint ptimisation, Constraints and SAT: Constraints: solvers and tools",

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.; 27th International Joint Conference on Artificial Intelligence and the 23rd European Conference on Artificial Intelligence, IJCAI-ECAI-18 ; Conference date: 13-07-2018 Through 19-07-2018",

year = "2018",

month = jul,

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",

url = "https://www.ijcai-18.org/",

}

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

A framework for constraint based local search using ESSENCE. / Akgun, Ozgur; Attieh, Saad Wasim A; Gent, Ian Philip et al.
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 proceeding › Conference contribution

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 - Conference code: 27/23

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.

KW - Constraints and SAT: constraint satisfaction

KW - Constraints and SAT: modeling; formulation

KW - Constraints and SAT: constraint ptimisation

KW - Constraints and SAT: Constraints: solvers and tools

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

T2 - 27th International Joint Conference on Artificial Intelligence and the 23rd European Conference on Artificial Intelligence

Y2 - 13 July 2018 through 19 July 2018

ER -

A framework for constraint based local search using ESSENCE

Abstract

Conference

Keywords

Access to Document

Fingerprint

Projects

Modelling and Optimisation with Graphs: Modelling and Optimisation with Graphs

Profiles

Ozgur Akgun

Christopher Anthony Jefferson

Cite this