Skip to main content

TS

Decompositions of all different, global cardinality and related constraints

Authors

Christian Bessiere, Georgios Katsirelos, Nina Narodytska, Claude-Guy Quimper and Toby Walsh

LIRMM

CNRS

NICTA

UNSW

Ecole Polytechnique de Montreal
Montreal
Canada

Abstract

We show that some common and important global constraints like \alldiff and \gcc can be decomposed into simple arithmetic constraints on which we achieve bound or range consistency, and in some cases even greater pruning. These decompositions can be easily added to new solvers. They also provide other constraints with access to the state of the propagator by sharing of variables. Such sharing can be used to improve propagation between constraints. We report experiments with our decomposition in a pseudo-Boolean solver.

BibTeX Entry

  @inproceedings{Bessiere_KNQW_09,
    author           = {Bessiere, Christian and Katsirelos, Georgios and Narodytska, Nina and Quimper, Claude-Guy and Walsh,
                        Toby},
    month            = jul,
    year             = {2009},
    keywords         = {constraint satisfaction, satisfiability},
    title            = {Decompositions of All Different, Global Cardinality and Related Constraints},
    booktitle        = {International Joint Conference on Artificial Intelligence IJCAI-09},
    address          = {Pasadena, CA, USA}
  }

Download

Served by Apache on Linux on seL4.