Sequential precede chain for value symmetry elimination

Graeme Gange; Peter J. Stuckey

doi:10.1007/978-3-319-98334-9_10

Sequential precede chain for value symmetry elimination

Graeme Gange, Peter J. Stuckey

Department of Data Science & AI

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

3 Citations (Scopus)

Abstract

The main global constraint used for removing value symmetries is the VALUE-PRECEDE-CHAIN constraint which forces the first occurences of values in an ordered list to be appear in order. We introduce the seq-precede-chain constraint for the restricted, but common, case where the values are 1,2, … , k, and variables in the constraint do not take values higher than k. We construct an efficient domain consistent propagator for this constraint, and show how we can generate explanations for its propagation. This leads us to an efficient domain consistent decomposition. We show how we can map any VALUE-PRECEDE-CHAIN to use instead SEQ-PRECEDE-CHAIN. Experiments show that the new propagator and decomposition are better than existing approachs to propagating VALUE-PRECEDE-CHAIN.

Original language	English
Title of host publication	Principles and Practice of Constraint Programming
Subtitle of host publication	24th International Conference, CP 2018 Lille, France, August 27–31, 2018 Proceedings
Editors	John Hooker
Place of Publication	Cham Switzerland
Publisher	Springer
Pages	144-159
Number of pages	16
ISBN (Electronic)	9783319983349
ISBN (Print)	9783319983332
DOIs	https://doi.org/10.1007/978-3-319-98334-9_10
Publication status	Published - 2018
Event	International Conference on Principles and Practice of Constraint Programming 2018 - Lille, France Duration: 27 Aug 2018 → 31 Aug 2018 Conference number: 24th http://cp2018.a4cp.org/

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	11008
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	International Conference on Principles and Practice of Constraint Programming 2018
Abbreviated title	CP 2018
Country/Territory	France
City	Lille
Period	27/08/18 → 31/08/18
Internet address	http://cp2018.a4cp.org/

Access to Document

10.1007/978-3-319-98334-9_10

Cite this

Gange, G., & Stuckey, P. J. (2018). Sequential precede chain for value symmetry elimination. In J. Hooker (Ed.), Principles and Practice of Constraint Programming : 24th International Conference, CP 2018 Lille, France, August 27–31, 2018 Proceedings (pp. 144-159). (Lecture Notes in Computer Science ; Vol. 11008 ). Springer. https://doi.org/10.1007/978-3-319-98334-9_10

@inproceedings{b6e40caa6c324d95b42bfc1bab5a5605,

title = "Sequential precede chain for value symmetry elimination",

abstract = "The main global constraint used for removing value symmetries is the VALUE-PRECEDE-CHAIN constraint which forces the first occurences of values in an ordered list to be appear in order. We introduce the seq-precede-chain constraint for the restricted, but common, case where the values are 1,2, … , k, and variables in the constraint do not take values higher than k. We construct an efficient domain consistent propagator for this constraint, and show how we can generate explanations for its propagation. This leads us to an efficient domain consistent decomposition. We show how we can map any VALUE-PRECEDE-CHAIN to use instead SEQ-PRECEDE-CHAIN. Experiments show that the new propagator and decomposition are better than existing approachs to propagating VALUE-PRECEDE-CHAIN.",

author = "Graeme Gange and Stuckey, {Peter J.}",

year = "2018",

doi = "10.1007/978-3-319-98334-9_10",

language = "English",

isbn = "9783319983332",

series = "Lecture Notes in Computer Science ",

publisher = "Springer",

pages = "144--159",

editor = "Hooker, {John }",

booktitle = "Principles and Practice of Constraint Programming",

note = "International Conference on Principles and Practice of Constraint Programming 2018, CP 2018 ; Conference date: 27-08-2018 Through 31-08-2018",

url = "http://cp2018.a4cp.org/",

}

Gange, G & Stuckey, PJ 2018, Sequential precede chain for value symmetry elimination. in J Hooker (ed.), Principles and Practice of Constraint Programming : 24th International Conference, CP 2018 Lille, France, August 27–31, 2018 Proceedings. Lecture Notes in Computer Science , vol. 11008 , Springer, Cham Switzerland, pp. 144-159, International Conference on Principles and Practice of Constraint Programming 2018, Lille, France, 27/08/18. https://doi.org/10.1007/978-3-319-98334-9_10

Sequential precede chain for value symmetry elimination. / Gange, Graeme; Stuckey, Peter J.
Principles and Practice of Constraint Programming : 24th International Conference, CP 2018 Lille, France, August 27–31, 2018 Proceedings. ed. / John Hooker. Cham Switzerland: Springer, 2018. p. 144-159 (Lecture Notes in Computer Science ; Vol. 11008 ).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

T1 - Sequential precede chain for value symmetry elimination

AU - Gange, Graeme

AU - Stuckey, Peter J.

N1 - Conference code: 24th

PY - 2018

Y1 - 2018

N2 - The main global constraint used for removing value symmetries is the VALUE-PRECEDE-CHAIN constraint which forces the first occurences of values in an ordered list to be appear in order. We introduce the seq-precede-chain constraint for the restricted, but common, case where the values are 1,2, … , k, and variables in the constraint do not take values higher than k. We construct an efficient domain consistent propagator for this constraint, and show how we can generate explanations for its propagation. This leads us to an efficient domain consistent decomposition. We show how we can map any VALUE-PRECEDE-CHAIN to use instead SEQ-PRECEDE-CHAIN. Experiments show that the new propagator and decomposition are better than existing approachs to propagating VALUE-PRECEDE-CHAIN.

AB - The main global constraint used for removing value symmetries is the VALUE-PRECEDE-CHAIN constraint which forces the first occurences of values in an ordered list to be appear in order. We introduce the seq-precede-chain constraint for the restricted, but common, case where the values are 1,2, … , k, and variables in the constraint do not take values higher than k. We construct an efficient domain consistent propagator for this constraint, and show how we can generate explanations for its propagation. This leads us to an efficient domain consistent decomposition. We show how we can map any VALUE-PRECEDE-CHAIN to use instead SEQ-PRECEDE-CHAIN. Experiments show that the new propagator and decomposition are better than existing approachs to propagating VALUE-PRECEDE-CHAIN.

UR - http://www.scopus.com/inward/record.url?scp=85053168951&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-98334-9_10

DO - 10.1007/978-3-319-98334-9_10

M3 - Conference Paper

AN - SCOPUS:85053168951

SN - 9783319983332

T3 - Lecture Notes in Computer Science

SP - 144

EP - 159

BT - Principles and Practice of Constraint Programming

A2 - Hooker, John

PB - Springer

CY - Cham Switzerland

T2 - International Conference on Principles and Practice of Constraint Programming 2018

Y2 - 27 August 2018 through 31 August 2018

ER -

Sequential precede chain for value symmetry elimination

Abstract

Publication series

Conference

Access to Document

Other files and links

Towards reliability in combinatorial optimisation

Cite this

Sequential precede chain for value symmetry elimination

Abstract

Publication series

Conference

Access to Document

Other files and links

Projects

Towards reliability in combinatorial optimisation

Cite this