Same-Relation Constraints

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

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    4 Citations (Scopus)

    Abstract

    The ALLDIFFERFINT 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 languageEnglish
    Title of host publicationPrinciples and Practice of Constraint Programming
    EditorsIP Gent
    Place of PublicationBerlin
    PublisherSpringer
    Pages470-485
    Number of pages16
    ISBN (Print)978-3-642-04243-0
    Publication statusPublished - 2009
    Event15th International Conference on Principles and Practice of Constraint Programming - Lisbon, Portugal
    Duration: 20 Sep 200924 Sep 2009
    http://centria.di.fct.unl.pt/conferences/cp2009/

    Conference

    Conference15th International Conference on Principles and Practice of Constraint Programming
    Abbreviated titleCP 2009
    CountryPortugal
    CityLisbon
    Period20/09/0924/09/09
    Internet address

    Keywords

    • ARC

    Cite this