A generic method for identifying and exploiting dominance relations

Geoffrey Chu; Peter J. Stuckey

doi:10.1007/978-3-642-33558-7_4

A generic method for identifying and exploiting dominance relations

Geoffrey Chu, Peter J. Stuckey

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

13 Citations (Scopus)

Abstract

Many constraint problems exhibit dominance relations which can be exploited for dramatic reductions in search space. Dominance relations are a generalization of symmetry and conditional symmetry. However, unlike symmetry breaking which is relatively well studied, dominance breaking techniques are not very well understood and are not commonly applied. In this paper, we present formal definitions of dominance breaking, and a generic method for identifying and exploiting dominance relations via dominance breaking constraints. We also give a generic proof of the correctness and compatibility of symmetry breaking constraints, conditional symmetry breaking constraints and dominance breaking constraints.

Original language	English
Title of host publication	Principles and Practice of Constraint Programming - 18th International Conference, CP 2012, Proceedings
Publisher	Springer
Pages	6-22
Number of pages	17
ISBN (Print)	9783642335570
DOIs	https://doi.org/10.1007/978-3-642-33558-7_4
Publication status	Published - 7 Nov 2012
Externally published	Yes
Event	International Conference on Principles and Practice of Constraint Programming 2012 - Quebec, Canada Duration: 8 Oct 2012 → 12 Oct 2012 Conference number: 18th http://archive.a4cp.org/cp2012/

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	7514 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	International Conference on Principles and Practice of Constraint Programming 2012
Abbreviated title	CP 2012
Country/Territory	Canada
City	Quebec
Period	8/10/12 → 12/10/12
Internet address	http://archive.a4cp.org/cp2012/

Access to Document

10.1007/978-3-642-33558-7_4

Cite this

Chu, G., & Stuckey, P. J. (2012). A generic method for identifying and exploiting dominance relations. In Principles and Practice of Constraint Programming - 18th International Conference, CP 2012, Proceedings (pp. 6-22). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7514 LNCS). Springer. https://doi.org/10.1007/978-3-642-33558-7_4

Chu, Geoffrey ; Stuckey, Peter J. / A generic method for identifying and exploiting dominance relations. Principles and Practice of Constraint Programming - 18th International Conference, CP 2012, Proceedings. Springer, 2012. pp. 6-22 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{28384a9160094de7901e78007f5bbae6,

title = "A generic method for identifying and exploiting dominance relations",

abstract = "Many constraint problems exhibit dominance relations which can be exploited for dramatic reductions in search space. Dominance relations are a generalization of symmetry and conditional symmetry. However, unlike symmetry breaking which is relatively well studied, dominance breaking techniques are not very well understood and are not commonly applied. In this paper, we present formal definitions of dominance breaking, and a generic method for identifying and exploiting dominance relations via dominance breaking constraints. We also give a generic proof of the correctness and compatibility of symmetry breaking constraints, conditional symmetry breaking constraints and dominance breaking constraints.",

author = "Geoffrey Chu and Stuckey, {Peter J.}",

year = "2012",

month = nov,

day = "7",

doi = "10.1007/978-3-642-33558-7_4",

language = "English",

isbn = "9783642335570",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "6--22",

booktitle = "Principles and Practice of Constraint Programming - 18th International Conference, CP 2012, Proceedings",

note = "International Conference on Principles and Practice of Constraint Programming 2012, CP 2012 ; Conference date: 08-10-2012 Through 12-10-2012",

url = "http://archive.a4cp.org/cp2012/",

}

Chu, G & Stuckey, PJ 2012, A generic method for identifying and exploiting dominance relations. in Principles and Practice of Constraint Programming - 18th International Conference, CP 2012, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7514 LNCS, Springer, pp. 6-22, International Conference on Principles and Practice of Constraint Programming 2012, Quebec, Quebec, Canada, 8/10/12. https://doi.org/10.1007/978-3-642-33558-7_4

A generic method for identifying and exploiting dominance relations. / Chu, Geoffrey; Stuckey, Peter J.
Principles and Practice of Constraint Programming - 18th International Conference, CP 2012, Proceedings. Springer, 2012. p. 6-22 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7514 LNCS).

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

TY - GEN

T1 - A generic method for identifying and exploiting dominance relations

AU - Chu, Geoffrey

AU - Stuckey, Peter J.

N1 - Conference code: 18th

PY - 2012/11/7

Y1 - 2012/11/7

N2 - Many constraint problems exhibit dominance relations which can be exploited for dramatic reductions in search space. Dominance relations are a generalization of symmetry and conditional symmetry. However, unlike symmetry breaking which is relatively well studied, dominance breaking techniques are not very well understood and are not commonly applied. In this paper, we present formal definitions of dominance breaking, and a generic method for identifying and exploiting dominance relations via dominance breaking constraints. We also give a generic proof of the correctness and compatibility of symmetry breaking constraints, conditional symmetry breaking constraints and dominance breaking constraints.

AB - Many constraint problems exhibit dominance relations which can be exploited for dramatic reductions in search space. Dominance relations are a generalization of symmetry and conditional symmetry. However, unlike symmetry breaking which is relatively well studied, dominance breaking techniques are not very well understood and are not commonly applied. In this paper, we present formal definitions of dominance breaking, and a generic method for identifying and exploiting dominance relations via dominance breaking constraints. We also give a generic proof of the correctness and compatibility of symmetry breaking constraints, conditional symmetry breaking constraints and dominance breaking constraints.

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

U2 - 10.1007/978-3-642-33558-7_4

DO - 10.1007/978-3-642-33558-7_4

M3 - Conference Paper

AN - SCOPUS:84868282340

SN - 9783642335570

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 6

EP - 22

BT - Principles and Practice of Constraint Programming - 18th International Conference, CP 2012, Proceedings

PB - Springer

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

Y2 - 8 October 2012 through 12 October 2012

ER -

Chu G, Stuckey PJ. A generic method for identifying and exploiting dominance relations. In Principles and Practice of Constraint Programming - 18th International Conference, CP 2012, Proceedings. Springer. 2012. p. 6-22. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-33558-7_4

A generic method for identifying and exploiting dominance relations

Abstract

Publication series

Conference

Access to Document

Other files and links

Cite this