Skip to main content

TS

Decomposition of the NVALUE constraint

Authors

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

LIRMM

NICTA

UNSW

Ecole Polytechnique de Montreal
Montreal
Canada

Abstract

We study decompositions of NVALUE, a global constraint that can be used to model a wide range of problems where values need to be counted. Such decompositions are useful as few constraints toolkits provide propagators for this global constraint. One of our decompositions maintains a global view as enforcing bound consistency on the decomposition achieves bound consistency on the original global constraint. Our experiments demonstrate that this decomposition is ef´Čücient enough to be used in practice

BibTeX Entry

  @misc{Bessiere_KNQW_09_2,
    author           = {Bessiere, Christian and Katsirelos, Georgios and Narodytska, Nina and Quimper, Claude-Guy and Walsh,
                        Toby},
    month            = sep,
    year             = {2009},
    keywords         = {global constraints, decompositions},
    title            = {Decomposition of the {NVALUE} Constraint},
    type             = {Other Conference Presentation},
    booktitle        = { Proceedings of the CP'09 Eighth International Workshop on Constraint Modelling and Reformulation},
    address          = {Lisbon, Portugal}
  }

Download

Served by Apache on Linux on seL4.