Sequential precede chain for value symmetry elimination

Graeme Gange, Peter J. Stuckey

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

3 Citations (Scopus)


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 languageEnglish
Title of host publicationPrinciples and Practice of Constraint Programming
Subtitle of host publication24th International Conference, CP 2018 Lille, France, August 27–31, 2018 Proceedings
EditorsJohn Hooker
Place of PublicationCham Switzerland
Number of pages16
ISBN (Electronic)9783319983349
ISBN (Print)9783319983332
Publication statusPublished - 2018
EventInternational Conference on Principles and Practice of Constraint Programming 2018 - Lille, France
Duration: 27 Aug 201831 Aug 2018
Conference number: 24th

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


ConferenceInternational Conference on Principles and Practice of Constraint Programming 2018
Abbreviated titleCP 2018
Internet address

Cite this