# Decompositions Of All Different, Global Cardinality And Related Constraints

Christian Bessiere∗
LIRMM, CNRS
Montpellier bessiere@lirmm.fr George Katsirelos†
NICTA, Sydney gkatsi@gmail.com Nina Narodytska†
NICTA and UNSW
Sydney ninan@cse.unsw.edu.au Claude-Guy Quimper EPM, Montr´eal cquimper@gmail.com Toby Walsh†
NICTA and UNSW
Sydney toby.walsh@nicta.com.au

## Abstract

We show that some common and important global constraints like ALL-DIFFERENT 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.

1 Introduction Global constraints allow users to specify patterns that commonly occur in problems. One of the oldest and most useful is the ALL-DIFFERENT constraint [Lauriere, 1978; R´egin, 1994]. This ensures that a set of variables are pairwise different. Global constraints can often be decomposed into more primitive constraints. For example, the ALL-DIFFERENT constraint can be decomposed into a clique of binary inequalities. However, such decompositions usually do not provide a global view and are thus not able to achieve levels of local consistency, such as bound and domain consistency. Considerable effort has therefore been invested in developing efficient propagation algorithms to reason globally about such constraints. For instance, several different propagation algorithms have been developed for the ALL-DIFFERENT constraint [R´egin, 1994; Leconte, 1996; Puget, 1998; Mehlhorn and Thiel, 2000; Lopez-Ortiz *et al.*, 2003]. In this paper, we show that several important global constraints including ALL-DIFFERENT can be decomposed into simple arithmetic constraints whilst still providing a global view since bound consistency can be achieved.

There are many reasons why such decompositions are interesting. First, it is very surprising that complex propagation algorithms can be simulated by simple decompositions. In
∗Supported by the project ANR-06-BLAN-0383-02.

†NICTA is funded by the Australian Government through the Department of Broadband, Communications and the Digital Economy and the Australian Research Council.

many cases, we show that reasoning with the decompositions is of similar complexity to existing monolithic propagation algorithms. Second, these decompositions can be easily added to a new solver. For example, we report experiments here using these decompositions in a state of the art pseudo-Boolean solver. We could just as easily use them in an ILP solver.

Third, introduced variables in these decompositions give access to the state of the propagator. Sharing of such variables between decompositions can increase propagation. Fourth, these decomposition provide a fresh perspective to propagating global constraints that may be useful. For instance, our decompositions of the ALL-DIFFERENT constraint suggest learning nogoods based on small Hall intervals.

## 2 Formal Background

A constraint satisfaction problem (CSP) consists of a set of variables, each with a finite domain of values, and a set of constraints specifying allowed combinations of values for some subset of variables. We use capitals for variables and lower case for values. We write dom(X) for the domain of possible values for X, min(X) for the smallest value in dom(X), max(X) for the greatest, and range(X) for the interval [min(X), max(X)]. A *global constraint* is one in which the number of variables n is a parameter. For instance, the global ALL-DIFFERENT([X1, . . . , Xn]) constraint ensures that Xi 6= Xj for any i < j [R´egin, 1994].

We will assume values range over 1 to d.

Constraint solvers typically use backtracking search to explore the space of partial assignments. After each assignment, propagation algorithms prune the search space by enforcing local consistency properties like domain or bound consistency. A constraint is domain consistent (DC) iff when a variable is assigned any of the values in its domain, there exist compatible values in the domains of all the other variables of the constraint. Such an assignment is called a *support*. A constraint is *bound consistent* (BC) iff when a variable is assigned the minimum or maximum value in its domain, there exist compatible values between the minimum and maximum domain value for all the other variables. Such an assignment is called a *bound support*. Finally, between domain and bound consistency is range consistency. A constraint is range consistent (RC) iff when a variable is assigned any value in its domain, there exists a bound support.

Constraint solvers usually enforce local consistency after arXiv:0905.3755v1 [cs.AI] 22 May 2009