Same-Relation Constraints

Christopher Jefferson; Serdar Kadioglu; Karen E. Petrie; Meinolf Sellmann; Stanislav Zivny

doi:10.1007/978-3-642-04244-7_38

Same-Relation Constraints

Christopher Jefferson, Serdar Kadioglu, Karen E. Petrie, Meinolf Sellmann, Stanislav Zivny

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

The ALLDIFFERENT constraint was one of the first global constraints [17] and it enforces the conjunction of one binary constraint, the not-equal constraint, for every pair of variables. By looking at the set of all pairwise not-equal relations at the same time, AllDifferent offers greater filtering power. The natural question arises whether we can generally leverage the knowledge that sets of pairs of variables all share the same relation. This paper studies exactly this question. We study in particular special constraint graphs like cliques, complete bipartite graphs, and directed acyclic graphs, whereby we always assume that the same constraint is enforced on all edges in the graph. In particular, we study whether there exists a tractable GAC propagator for these global Same-Relation constraints and show that AllDifferent is a huge exception: most Same-Relation Constraints pose NP-hard filtering problems. We present algorithms, based on AC-4 and AC-6, for one family of Same-Relation Constraints, which do not achieve GAC propagation but outperform propagating each constraint individually in both theory and practice.

Original language	English
Title of host publication	Principles and Practice of Constraint Programming - CP 2009: 15th International Conference, CP 2009 Lisbon, Portugal, September 20-24, 2009: Proceedings
Editors	I. P. Gent
Publisher	Springer
Pages	470-485
Number of pages	16
ISBN (Print)	978-3-642-04243-0
DOIs	https://doi.org/10.1007/978-3-642-04244-7_38
Publication status	Published - 2009

Publication series

Name	Lecture Notes in Computer Science
Volume	5732
ISSN (Print)	0302-9743

Keywords

ARC

Access to Document

10.1007/978-3-642-04244-7_38

EP/C523229/1: Multidisciplinary Critical Mass in Computational Algebra and Applications
Linton, S. A. (PI), Gent, I. P. (CoI), Leonhardt, U. (CoI), Mackenzie, A. (CoI), Miguel, I. J. (CoI), Quick, M. (CoI) & Ruskuc, N. (CoI)
EPSRC
1/09/05 → 31/08/10
Project: Standard

Cite this

Jefferson, C., Kadioglu, S., Petrie, K. E., Sellmann, M., & Zivny, S. (2009). Same-Relation Constraints. In I. P. Gent (Ed.), Principles and Practice of Constraint Programming - CP 2009: 15th International Conference, CP 2009 Lisbon, Portugal, September 20-24, 2009: Proceedings (pp. 470-485). (Lecture Notes in Computer Science; Vol. 5732). Springer. https://doi.org/10.1007/978-3-642-04244-7_38

@inproceedings{01a3954dcec445e284eba495d5ccd76f,

title = "Same-Relation Constraints",

abstract = "The ALLDIFFERENT constraint was one of the first global constraints [17] and it enforces the conjunction of one binary constraint, the not-equal constraint, for every pair of variables. By looking at the set of all pairwise not-equal relations at the same time, AllDifferent offers greater filtering power. The natural question arises whether we can generally leverage the knowledge that sets of pairs of variables all share the same relation. This paper studies exactly this question. We study in particular special constraint graphs like cliques, complete bipartite graphs, and directed acyclic graphs, whereby we always assume that the same constraint is enforced on all edges in the graph. In particular, we study whether there exists a tractable GAC propagator for these global Same-Relation constraints and show that AllDifferent is a huge exception: most Same-Relation Constraints pose NP-hard filtering problems. We present algorithms, based on AC-4 and AC-6, for one family of Same-Relation Constraints, which do not achieve GAC propagation but outperform propagating each constraint individually in both theory and practice.",

keywords = "ARC",

author = "Christopher Jefferson and Serdar Kadioglu and Petrie, {Karen E.} and Meinolf Sellmann and Stanislav Zivny",

year = "2009",

doi = "10.1007/978-3-642-04244-7_38",

language = "English",

isbn = "978-3-642-04243-0",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "470--485",

editor = "Gent, {I. P.}",

booktitle = "Principles and Practice of Constraint Programming - CP 2009: 15th International Conference, CP 2009 Lisbon, Portugal, September 20-24, 2009: Proceedings",

address = "Netherlands",

}

Jefferson, C, Kadioglu, S, Petrie, KE, Sellmann, M & Zivny, S 2009, Same-Relation Constraints. in IP Gent (ed.), Principles and Practice of Constraint Programming - CP 2009: 15th International Conference, CP 2009 Lisbon, Portugal, September 20-24, 2009: Proceedings. Lecture Notes in Computer Science, vol. 5732, Springer, pp. 470-485. https://doi.org/10.1007/978-3-642-04244-7_38

Same-Relation Constraints. / Jefferson, Christopher; Kadioglu, Serdar; Petrie, Karen E. et al.
Principles and Practice of Constraint Programming - CP 2009: 15th International Conference, CP 2009 Lisbon, Portugal, September 20-24, 2009: Proceedings. ed. / I. P. Gent. Springer, 2009. p. 470-485 (Lecture Notes in Computer Science; Vol. 5732).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Same-Relation Constraints

AU - Jefferson, Christopher

AU - Kadioglu, Serdar

AU - Petrie, Karen E.

AU - Sellmann, Meinolf

AU - Zivny, Stanislav

PY - 2009

Y1 - 2009

N2 - The ALLDIFFERENT constraint was one of the first global constraints [17] and it enforces the conjunction of one binary constraint, the not-equal constraint, for every pair of variables. By looking at the set of all pairwise not-equal relations at the same time, AllDifferent offers greater filtering power. The natural question arises whether we can generally leverage the knowledge that sets of pairs of variables all share the same relation. This paper studies exactly this question. We study in particular special constraint graphs like cliques, complete bipartite graphs, and directed acyclic graphs, whereby we always assume that the same constraint is enforced on all edges in the graph. In particular, we study whether there exists a tractable GAC propagator for these global Same-Relation constraints and show that AllDifferent is a huge exception: most Same-Relation Constraints pose NP-hard filtering problems. We present algorithms, based on AC-4 and AC-6, for one family of Same-Relation Constraints, which do not achieve GAC propagation but outperform propagating each constraint individually in both theory and practice.

AB - The ALLDIFFERENT constraint was one of the first global constraints [17] and it enforces the conjunction of one binary constraint, the not-equal constraint, for every pair of variables. By looking at the set of all pairwise not-equal relations at the same time, AllDifferent offers greater filtering power. The natural question arises whether we can generally leverage the knowledge that sets of pairs of variables all share the same relation. This paper studies exactly this question. We study in particular special constraint graphs like cliques, complete bipartite graphs, and directed acyclic graphs, whereby we always assume that the same constraint is enforced on all edges in the graph. In particular, we study whether there exists a tractable GAC propagator for these global Same-Relation constraints and show that AllDifferent is a huge exception: most Same-Relation Constraints pose NP-hard filtering problems. We present algorithms, based on AC-4 and AC-6, for one family of Same-Relation Constraints, which do not achieve GAC propagation but outperform propagating each constraint individually in both theory and practice.

KW - ARC

U2 - 10.1007/978-3-642-04244-7_38

DO - 10.1007/978-3-642-04244-7_38

M3 - Conference contribution

SN - 978-3-642-04243-0

T3 - Lecture Notes in Computer Science

SP - 470

EP - 485

BT - Principles and Practice of Constraint Programming - CP 2009: 15th International Conference, CP 2009 Lisbon, Portugal, September 20-24, 2009: Proceedings

A2 - Gent, I. P.

PB - Springer

ER -

Same-Relation Constraints

Abstract

Publication series

Keywords

Access to Document

Fingerprint

Projects

EP/C523229/1: Multidisciplinary Critical Mass in Computational Algebra and Applications

Cite this