On Global Warming
(Softening Global Constraints)
Willem Jan van Hoeve1 , Gilles Pesant2,3 and Louis-Martin Rousseau2,3

arXiv:cs/0408023v1 [cs.AI] 9 Aug 2004

1

CWI, P.O. Box 94079, 1090 GB Amsterdam, The Netherlands
W.J.van.Hoeve@cwi.nl
2
École Polytechnique de Montréal, Montreal, Canada
3
Centre for Research on Transportation (CRT),
Université de Montréal, C.P. 6128, succ. Centre-ville, Montreal, H3C 3J7, Canada
{pesant,louism}@crt.umontreal.ca

Abstract. We describe soft versions of the global cardinality constraint
and the regular constraint, with efficient filtering algorithms maintaining
domain consistency. For both constraints, the softening is achieved by
augmenting the underlying graph. The softened constraints can be used
to extend the meta-constraint framework for over-constrained problems
proposed by Petit, Régin and Bessière.

1

Introduction

Constraint Programming (CP) is a widely used and efficient technique to solve
combinatorial optimization problems. However in practice many problems are
over-constrained (intrinsically or from being badly stated). Several frameworks
have been proposed to handle over-constrained problems, mostly by introducing
soft constraints that are allowed to be (partially) violated. The most well-known
framework is the Partial Constraint Satisfaction Problem framework (PCSP [8]),
which includes the Max-CSP framework that tries to maximize the number of
satisfied constraints. Since in this framework all constraints are either violated
or satisfied, this objective is equivalent to minimizing the number of violations.
It has been extended to the Weighted-CSP [10,11], associating a degree of violation (not just a boolean value) to each constraint and minimizing the sum
of all weighted violations. The Possibilistic-CSP [18] associates a preference to
each constraint (a real value between 0 and 1) representing its importance. The
objective of the framework is the hierarchical satisfaction of the most important
constraints, that is, the minimization of the highest preference level for a violated
constraint. The Fuzzy-CSP [6,7] is somewhat similar to the Possibilistic-CSP
but here a preference is associated to each tuple of each constraint. A preference
value of 0 means the constraint is highly violated and 1 stands for satisfaction.
The objective is the maximization of the smallest preference value induced by
a variable assignment. The last two frameworks are different from the previous
ones since the aggregation operator is a min/max function instead of addition.
Max-CSPs are typically encoded and solved with one of two generic paradigms:
valued-CSPs [19] and semi-rings [5].

Another approach to model and solve over-constrained problems involves
Meta-Constraints [13]. The idea behind this technique is to introduce a set
of domain variables Z that capture the violation cost of each soft constraint.
By correctly constraining these variables it is possible to replicate the previous
frameworks and even to extend the modeling capability to capture other types
of violation measures. Namely the authors argue that although the Max-CSP
family of frameworks is quite efficient to capture local violation measures it is
not as adequate to model violation costs involving several soft constraints simultaneously. By defining (possibly global) constraints on Z such a behaviour
can be easily achieved. The authors propose to replace each soft constraint Si
present in a model by a disjunctive constraint specifying that either zi = 0 and
the constraint Si is hard or zi > 0 and Si is violated. This technique allows the
resolution of over-constrained problem within traditional CP solvers.
Comparatively few efforts have been invested in developing soft versions of
common global constraints [14,4,9]. Global constraints are often key elements in
successfully modeling real applications and being able to easily and effectively
soften such constraints would yield a significant improvement in flexibility. In
this paper we study two global constraints: the widely known global cardinality
constraint (gcc) [15] and the new regular [12] constraint. For each of these we
propose new violation measures and provide the corresponding filtering algorithms to achieve domain consistency. All the constraint softening is achieved by
enriching the underlying graph representation with additional arcs that represent
possible relaxations of the constraint. Violation costs are then associated to these
new arcs and known graph algorithms are used to achieve domain consistency.
The two constraints studied in this paper are useful to model and solve
personnel rostering problems (PRP). The PRP objective is typically to distribute
a set of working shifts (or days off) to a set of employees every day over a
planning horizon (a set of days). The gcc is a perfect tool to restrict the number
of work shifts of each type (Day, Evening, and Night for instance) performed by
each employee. Other types of constraints involve sequences of shifts over time,
typically forbidding non ergonomic schedules. The regular constraint has the
expressive power necessary to cope with the complex regulations found in many
organizations. Since most real rostering applications are over-constrained (due
to lack of personnel or over-optimistic scheduling objectives), soft versions of
the gcc and regular constraints promise to significantly improve our modelling
flexibility.
This paper is organized as follows. Section 2 presents background information on Constraint Programming and the softening of (global) constraints. In
Section 3 and 4 we describe the softening of the gcc and the regular constraint
respectively. Both constraints are softened with respect to two violation measures. We also provide corresponding filtering algorithms achieving domain consistency. Section 5 discusses the aggregation of several soft (global) constraints
by meta-constraints. Finally, a conclusion is given in Section 6.

2

Background

We assume familiarity with the basic concepts of constraint programming. For
a thorough explanation of constraint programming, see [2].
A constraint satisfaction problem (CSP) consists of a finite set of variables
X = {x1 , . . . , xn } with finite domains D = {D1 , . . . , Dn } such that xi ∈ Di
for all i, together with a finite set of constraints C, each on a subset of X. A
constraint C ∈ C is defined as a subset of the Cartesian product of the domains
of the variables that are in C. A tuple (d1 , . . . , dn ) ∈ D1 × · · · × Dn is a solution
to a CSP if for every constraint C ∈ C on the variables xi1 , . . . , xik we have
(di1 , . . . , dik ) ∈ C. A constraint optimization problem (COP) is a CSP together
with an objective function to be optimized. A solution to a COP is a solution
to the corresponding CSP that has an optimal objective function value.
Definition 1 (Domain consistency). A constraint C on the variables x1 , . . . ,
xk is called domain consistent if for each variable xi and value di ∈ Di , there
exist values d1 , . . . , di−1 , di+1 , . . . , dk in D1 , . . . , Di−1 , Di+1 , . . . , Dk , such that
(d1 , . . . , dk ) ∈ C.
Our definition of domain consistency corresponds to hyper-arc consistency or
generalized arc consistency, which are also often used in the literature.
Definition 2 (Consistent CSP). A CSP is domain consistent if all its constraints are domain consistent. A CSP is inconsistent if it has no solution. Similarly for a COP.
When a CSP is inconsistent it is also said to be over-constrained. It is then
natural to identify soft constraints, that are allowed to be violated, and minimize
the total violation according to some criteria. For each soft constraint C, we
introduce a function that measures the violation, and has the following form:
violationC : D1 × · · · × Dn → N.
This approach has been introduced in [14] and was developed further in [4].
There may be several natural ways to evaluate the degree to which a global
constraint is violated and these are not equivalent usually. A standard measure
is the variable-based cost:
Definition 3 (Variable-based cost). Given a constraint C on the variables
x1 , . . . , xk and an instantiation d1 , . . . , dk with di ∈ Di , the variable-based cost
of violation of C is the minimum number of variables that need to change their
value in order to satisfy the constraint.
Alternative measures exist for specific constraints. For example, if a constraint
is expressible as a conjunction of binary constraints, the cost may be defined as
the number of these binary constraints that are violated. For the soft gcc and
the soft regular constraint, we will introduce new violation measures, that are
likely to be more effective in practical applications.

3

Soft Global Cardinality Constraint

A global cardinality constraint (gcc) on a set of variables specifies the minimum
and maximum number of times each value in the union of their domains should
be assigned to these variables. Régin developed a domain consistency algorithm
for the gcc, making use of network flows [15]. A variant of the gcc is the costgcc, which can be seen as a weighted version of the gcc [16,17]. For the cost-gcc
a weight is assigned to each variable-value assignment and the goal is to satisfy
the gcc with minimum total cost.
Throughout this section, we will use the following notation (unless specified
otherwise). Let X denote a set of variables {x1 , . . . , xn } with respective finite
domains D1 , . . . , Dn . We define DX = ∪i∈{1,...,n} Di and we assume a fixed but
arbitrary ordering on DX . For d ∈ DX , let ld , ud ∈ N, with ld ≤ ud . Finally, let
z be a variable with finite domain Dz , representing the cost of violation of the
gcc.
Definition 4 (Global cardinality constraint).
gcc(X, l, u) = {(d1 , . . . , dn ) | di ∈ Di , ld ≤ |{di | di = d}| ≤ ud ∀ d ∈ DX }.
We first give a generic definition for a soft version of the gcc.
Definition 5 (Soft global cardinality constraint).
˜ | di ∈ Di , d˜ ∈ Dz ,
soft gcc[⋆](X, l, u, z) = {(d1 , . . . , dn , d)
˜
violationsoft gcc[⋆] (d1 , . . . , dn ) ≤ d},
where ⋆ defines a violation measure for the gcc.
In order to define measures of violation for the gcc, it is convenient to introduce
the following functions.
Definition 6 (Overflow, underflow). Given gcc(X, l, u), define for all d ∈
DX

|{xi | xi = d}| − ud
if |{xi | xi = d}| ≥ ud ,
overflow(X, d) =
0
otherwise,

l − |{xi | xi = d}|
if |{xi | xi = d}| ≤ ld ,
underflow(X, d) = d
0
otherwise.
Let violationsoft gcc[var] denote the variable-based cost of violation (see Definition 3) of the gcc. The next lemma expresses violationsoft gcc[var] in terms of the
above functions.
Lemma 1. Given gcc(X, l, u),
violationsoft gcc[var] (X) = max

X

overflow(X, d),

X

d∈DX

d∈DX

!

underflow(X, d)

provided that
X

d∈DX

ld ≤ |X| ≤

X

d∈DX

ud .

(1)

Proof. The variable-based cost of violation corresponds
to the minimal numP
overflow(X,
d) = 0 and
ber
of
re-assignments
of
variables
until
both
d∈D
X
P
d)
=
0.
d∈DX underflow(X,
P
P
Assume d∈DX overflow(X, d) ≥ d∈DX underflow(X, d). Variables assigned
′
to values d′ ∈ DX with overflow(X, dP
) > 0 can be assigned to values d′′ ∈
′′
DX withPunderflow(X, d ) > 0, until d∈DX underflow(X, d) = 0. In order to
achieve d∈DX overflow(X, d) = 0, we still need to re-assign the other variables
assigned to valuesPd′ ∈ DX with overflow(X, d′ ) > 0. Hence, in total we need to
re-assign exactly d∈DX overflow(X,
d) variables.
P
P
Similarly when we assume d∈DX overflow(X, d) ≤ d∈DX underflow(X, d).
If (1) does not hold, there is no variable assignment that satisfies the gcc. 
Without assumption (1), the variable-based violation measure for the gcc cannot
be applied. Therefore, we introduce the following value-based violation measure,
which can also be applied when assumption (1) does not hold.
Definition 7 (Value-based cost). For gcc(X, l, u) the value-based cost of violation is
X
overflow(X, d) + underflow(X, d).
d∈DX

We denote the value-based violation measure for the gcc by violationsoft gcc[val] .
3.1

Graph Representation

First, we introduce the concept of a flow in a directed graph, following Schrijver [20, pp. 148–150].
A directed graph is a pair G = (V, A) where V is a finite set of vertices and
A is a family1 of ordered pairs from V , called arcs. For v ∈ V , let δ in (v) and
δ out (v) denote the family of arcs entering and leaving v respectively.
A (directed) walk in G is a sequence P = v0 , a1 , v1 , . . . , ak , vk where k ≥ 0,
v0 , v1 , . . . , vk ∈ V , a1 , . . . , ak ∈ A and ai = (vi−1 , vi ) for i = 1, . . . , k. If there
is no confusion, P may be denoted as P = v0 , v1 , . . . , vk . A (directed) walk is
called a (directed) path if v0 , . . . , vk are distinct. A closed (directed) walk, i.e.
v0 = vk , is called a (directed) circuit if v1 , . . . , vk are distinct.
Let s, t ∈ V . We apply a capacity function c : A → R+ , a demand function
d : A → R+ and a cost function w : A → R+ on the arcs. A function f : A → R
is called a feasible flow from s to t, or an s − t flow, if
d(a) ≤ f (a) ≤ c(a)
for each a ∈ A,
f (δ out (v)) = f (δ in (v)) for each v ∈ V \ {s, t},

(2)
(3)

P
where f (S) = a∈S f (a) for all S ⊆ A. Property (3) ensures flow conservation,
i.e. for a vertex v 6= s, t, the amount of flow entering v is equal to the amount of
flow leaving v. The value of an s − t flow f is defined as
value(f ) = f (δ out (s)) − f (δ in (s)).
1

A family is a set in which elements may occur more than once.

In other words, the value of a flow is the net amount of flow leaving s, which can
be shown to be equal to the net amount of flow entering t. The cost of a flow f
is defined as
X
cost(f ) =
w(a)f (a).
a∈A

A minimum-cost flow is a feasible s−t flow of minimum cost. The minimum-cost
flow problem is the problem of finding such a minimum-cost flow.

Theorem 1 ([15]). A solution to gcc(X, l, u) corresponds to a feasible s − t
flow of value n in the graph G = (V, A) with vertex set
V = X ∪ DX ∪ {s, t}
and edge set
A = As→X ∪ AX→DX ∪ ADX →t ,
where

As→X = {(s, xi ) | i ∈ {1, . . . , n}},
AX→DX = {(xi , d) | d ∈ Di , i ∈ {1, . . . , n}},
ADX →t = {(d, t) | d ∈ DX },

with demand function

and capacity function


 1 if a ∈ As→X ,
d(a) = 0 if a ∈ AX→DX ,

ld if a = (d, t) ∈ ADX →t ,

 1 if a ∈ As→X ,
c(a) = 1 if a ∈ AX→DX ,

ud if a = (d, t) ∈ ADX →t .

Example 1. Consider the CSP

x1 ∈ {1, 2}, x2 ∈ {1}, x3 ∈ {1, 2}, x4 ∈ {1},
gcc(X, l, u)
where X = {x1 , . . . , x4 }, l1 = 1, l2 = 3, u1 = 2 and u2 = 5. In Figure 1.a the
corresponding graph G for the gcc by applying the above procedure is presented.
3.2

Variable-Based Violation

For the variable-based violation measure, we adapt the graph G in the following
/ Di , i ∈ {1, . . . , n}}, with
way. We add the arc set ÃX→DX = {(xi , d) | d ∈
demand d(a) = 0, capacity c(a) = 1 for all arcs a ∈ ÃX→DX . Further, we apply
a cost function w : A → R, where

1 if a ∈ ÃX→DX ,
w(a) =
0 otherwise.
Let the resulting graph be denoted by Gvar .

(0,1) w =1

x1

(1,1)

,1)

x3

t

s

)
(3,5

(0,1)
(0
,1
)

,1)

)

(0

(1,1)
(1

(1,2

(0,1)

(1,2

(0,1)
x2 (
0,1
)w
=

(1

,1)

x3

2

x4

x4

a. original gcc

(1,1)

)

s

1

(1,1)

t

,1)
(0
(0,1)

)

,1

(1

1

x2

,1)

(0,1)

w =1

2

b. soft gcc[var]

1

(0,i

nf)

(1,2

w=

1

)

,1)

t

(0

(1,1)
(1

)
(3,5

(0,1)

(0,1)

x3

)

(3,5

(0,1)
(0
,1)

s

x2

1)

,
(1

(0,1)

(0
,1)

(1,1)

1

,1)
(0

,1)
(0

1)

,
(1

x1

(0,1)

,1)
(0

x1

2

nf)

w

=1

(0,i

x4
=1
(0,3) w

c. soft gcc[val]

Fig. 1. Graph representation for the gcc, the variable-based soft gcc and the
value-based soft gcc. Demand and capacity are indicated between parentheses
for each arc. Dashed arcs indicate the inserted weighted arcs.

Example 2. Consider the CSP
x1 ∈ {1, 2}, x2 ∈ {1}, x3 ∈ {1, 2}, x4 ∈ {1}, z ∈ {0, 1, . . . , 4}
soft gcc[var](X, l, u, z)
minimize z
where X = {x1 , . . . , x4 }, l1 = 1, l2 = 3, u1 = 2 and u2 = 5. In Figure 1.b the
graph Gvar for the soft gcc[var] is presented.
Theorem 2. A minimum-cost flow in the graph Gvar corresponds to a solution
to the soft gcc[var], minimizing the variable-based violation.
Proof. An assignment xi = d corresponds to the arc a = (xi , d) with f (a) = 1.
By construction, all variables need to be assigned to a value and the cost function exactly measures the variable-based cost of violation.

The graph Gvar corresponds to a particular instance of the cost-gcc [16,17].
Hence, we can apply the filtering procedures developed for that constraint directly to the soft gcc[var]. The soft gcc[var] also inherits from the cost-gcc
the time complexity
of achieving domain consistency, being O(n(m + n log n))
Pn
where m = i=1 |Di | and n = |X|.
Note that [4] also consider the variable-based cost measure for a different
version of the soft gcc. Their version considers the parameters l and u to be
variables too. Hence, the variable-based cost evaluation becomes a rather poor
measure, as we trivially can change l and u to satisfy the gcc. They fix this by
restricting the set of variables to consider to be the set X, which corresponds to
our situation. However, they do not provide a filtering algorithm for that case.
3.3

Value-Based Violation

For the value-based violation measure, we adapt the graph G in the following way.
We add arc sets Aunderflow = {(s, d) | d ∈ DX } and Aoverflow = {(d, t) | d ∈ DX },

with demand d(a) = 0 for all a ∈ Aunderflow ∪ Aoverflow and capacity

l if a = (s, d) ∈ Aunderflow ,
c(a) = d
∞ if a ∈ Aoverflow .
Further, we again apply a cost function w : A → R, where

1 if a ∈ Aunderflow ∪ Aoverflow ,
w(a) =
0 otherwise.
Let the resulting graph be denoted by Gval .
Example 3. Consider the CSP
x1 ∈ {1, 2}, x2 ∈ {1}, x3 ∈ {1, 2}, x4 ∈ {1}, z ∈ {0, 1, . . . , 5}
soft gcc[val](X, l, u, z)
minimize z
where X = {x1 , . . . , x4 }, l1 = 1, l2 = 2, u1 = 3 and u2 = 2. In Figure 1.c the
graph Gval for the soft gcc with respect to value-based cost is presented.
Theorem 3. A minimum-cost flow in the graph Gval corresponds to a solution
to the soft gcc[val], minimizing the value-based violation.
Proof. An assignment xi = d corresponds to the arc a = (xi , d) with f (a) = 1.
By construction, all variables need to be assigned to a value and the cost function exactly measures the value-based cost of violation.

Unfortunately, the graph Gval does not preserve the structure of the costgcc because of the arcs Aunderflow . Therefore we cannot blindly apply the same
filtering algorithms. However, it is still possible to design an efficient filtering
algorithm for the value-based soft gcc (in the same spirit of the filtering algorithm for the cost-gcc), based again on flow theory. For this, we need to introduce
the residual graph G f = (V, Af ) of a flow f on G = (V, A) (with respect to c and
d), where
Af = {a | a ∈ A, f (a) < c(a)} ∪ {a−1 | a ∈ A, f (a) > d(a)}.
Here a−1 = (v, u) if a = (u, v). We extend w to A−1 = {a−1 | a ∈ A} by defining
w(a−1 ) = −w(a) for each a ∈ A.
Theorem 4. Let f be a minimum-cost flow in Gval . Then soft gcc[val](X, l, u, z)
is domain consistent if and only if
min Dz ≥ cost(f )
and
cost(f ) + cost(SP(d, xi )) ≤ max Dz ∀(xi , d) ∈ AX→DX ,
where cost(SP(d, xi )) denotes the cost of a shortest path from d to xi in the
f
residual graph Gval
.

Proof. From flow theory [1] we know that, given a minimum-cost flow f in
Gval , if we enforce arc (xi , d) to be in a minimum-cost flow f˜ in Gval , cost(f˜) =
f
cost(f ) + cost(SP(d, xi )) where SP(d, xi ) is the shortest d − xi path in Gval
.
In order for a value d ∈ Di to be consistent, the cost of a minimum-cost flow
that uses (xi , d) should be less than or equal to max Dz . By the above fact, we
only need to compute a shortest path from d to xi instead of a new minimumcost flow.

A minimum-cost flow f inPGval can be computed in O(m(m + n log n)) time
(see [1]), where again m = ni=1 |Di | and n = |X|. Compared to the complexity
of the soft gcc[var], we have a factor m instead of n. This is because computing the flow for soft gcc[val] is dependent on the number of arcs m rather than
on the number variables n. A shortest d − xi path in Gval can be computed in
O(m + n log n) time. Hence the soft gcc with respect to the value-based violation measure can be made domain consistent in O((m − n)(m + n log n)) time
as we need to check m − n arcs for consistency.
When l = 0 in soft gcc[val](X, l, u, z), the arc set Aunderflow is empty. In
that case, Gval has a particular structure, i.e. the only costs appear on arcs from
DX to t. As pointed out in [9] for the soft alldifferent constraint, constraints
with this structure can be checked for consistency in O(nm) time, and domain
consistency can be achieved in O(m) time. The result is obtained by exploiting
the strongly connected components2 in Gval restricted to vertex sets X and DX .

4

Soft Regular Constraint

A regular constraint [12] on a fixed-length sequence of finite-domain variables
requires that the corresponding sequence of values taken by these variables belong to a given regular language. A deterministic finite automaton (DFA) may
be described by a 5-tuple M = (Q, Σ, δ, q0 , F ) where Q is a finite set of states,
Σ is an alphabet, δ : Q × Σ → Q is a partial transition function, q0 ∈ Q is
the initial state, and F ⊆ Q is the set of final (or accepting) states. A finite
sequence of symbols from an alphabet is called a string. Strings processed by
M and ending in an accepting state from F are said to belong to the language
defined by M , denoted L(M ). The languages recognized by DFAs are precisely
regular languages.
Given a sequence x = hx1 , x2 , . . . , xn i of finite-domain variables with respective domains D1 , D2 , . . . , Dn ⊆ Σ, there is a natural interpretation of the set
of possible instantiations of x, D1 × D2 × · · · × Dn , as a subset of all strings of
length n over Σ, Σ n . We are now ready to state the constraint.
Definition 8 (Regular language membership constraint). Let M =
(Q, Σ, δ, q0 , F ) denote a deterministic finite automaton and x a sequence of
finite-domain variables hx1 , x2 , . . . , xn i with respective domains D1 , D2 , . . . ,
2

A strongly connected component in a directed graph G = (V, A) is a subset of vertices
S ⊆ V such that there exists a directed u − v path in G for all u, v ∈ S.

Dn
⊆
Σ. Under a regular language membership constraint
regular(x, M ), any sequence of values taken by the variables of x corresponds
to a string in L(M ).
In [12], a domain consistency algorithm for the regular constraint processed
the sequence x with the automaton M , building a layered directed multi-graph
i
G = (N 1 , N 2 , . . . , N n+1 , A) where each layer N i = {q0i , q1i , . . . , q|Q|−1
} contains
a different node for each state of M and arcs only appear between consecutive
layers. Each arc corresponds to a consistent variable-value pair: there is an arc
from qki to qℓi+1 if and only if there exists some vj ∈ Di such that δ(qk , vj ) = qℓ
and the arc belongs to a path from q0 in the first layer to a member of F in
the last layer. The existence of such an arc, labeled vj , constitutes a support for
variable xi taking value vj .
For example, consider a sequence x of five variables with D1 = {a, b, c, o},
D2 = {b, o}, D3 = {a, c, o}, D4 = {a, b, o}, and D5 = {a}. Figure 2 gives
an automaton M (with its initial state labeled 1) and the resulting graph for
constraint regular(x, M ). As a result, value b is removed from D2 and D4 .
x1
1

a

o

2

5
b

a
b
1

b

3

6

c
4

7
c

x4
1

o
a

2

a

2

2
o
3

4

4

x5
1

a

1

2

a

2

o
3

3

5

o

a

4

3
4

3

a

6

6

6 a

7

7

7

N1

N2

N3

a

4

o

o

5

a

4
5 o

5

5

c

c
o

o

x3
o
a

1

c

3

5

b

c

o

o

o

o

b
c

a
o

x2
1

a

o

2

o

a
c

6

6

6

a
o

7

N4

o

7

7

N5

N6

Fig. 2. A DFA (left) and its layered directed graph G (right).

4.1

Cost Definition

We first give a generic definition for a soft version of the regular constraint.
Definition 9 (Soft regular language membership constraint). Let M =
(Q, Σ, δ, q0 , F ) denote a deterministic finite automaton and x a sequence of
finite-domain variables hx1 , x2 , . . . , xn i with respective domains D1 , D2 , . . . ,
Dn ⊆ Σ. Let z be a finite-domain variable of domain Dz ⊂ N representing the
cost of a violation and let d : Σ ⋆ ×Σ ⋆ → N be some distance function over strings.
Under a soft regular language membership constraint soft regular[d](x, M, z),
for any sequence of values σ taken by the variables of x we have
minσ′ ∈L(M) {d(σ, σ ′ )} = z.

Our first instantiation of the distance function yields the variable-based cost:
Definition 10 (Hamming distance). The number of positions in which two
strings of same length differ is called their Hamming distance.
Intuitively, such a distance represents the number of symbols we need to change
to go from one string to the other, or equivalently the number of variables whose
value must change. Using the Hamming distance for d in the previous definition,
z becomes the variable-based cost.
Another distance function that is often used with strings is the following:
Definition 11 (Edit distance). The smallest number of insertions, deletions,
and substitutions required to change one string into another is called the edit
distance.
It captures the fact that two strings that are identical except for one extra or
missing symbol should be considered close to one another. For example, the edit
distance between strings “bcdea” and “abcde” is two: insert an ’a’ at the front of
the first string and delete the ’a’ from its end. The Hamming distance between
the same strings is five: every symbol must be changed. Edit distance is probably
a better way to measure violations of a regular constraint. We provide a more
natural example in the area of rostering. Given a string, we call stretch a maximal
substring of identical values. We often need to impose restrictions on the length
of stretches of work shifts, and these can be expressed with a regular constraint.
Suppose stretches of a’s and b’s must each be of length 2 and consider the string
“abbaabbaab”: its Hamming distance to a string belonging to the corresponding
regular language is 5 since changing either the first a to a b or b to an a has a
domino effect on the following stretches; its edit distance is just 2 since we can
insert an a at the beginning to make a legal stretch of a’s and remove the b at
the end. In this case, the edit distance reflects the number of illegal stretches
whereas the Hamming distance is proportional to the length of the string.
4.2

Cost Evaluation and Cost-Based Filtering

For both cost measures, we proceed by modifying the layered directed graph
G built for the “hard” version of regular into graph Gvar . Before, we added
an arc from qki to qℓi+1 if δ(qk , vj ) = qℓ for some vj ∈ Di ; now we relax it
slightly to any vj ∈ Σ. This only makes a difference if the domains of the
variables are not initially full. Arcs are never removed in Gvar but their labels
are updated instead. The label of an arc (qki , qℓi+1 ) is generalized to the invariant
Vikℓ = {vj ∈ Di | δ(qk , vj ) = qℓ }; as values are removed from the domain of
variable xi , they are also removed from the corresponding Vikℓ ’s. The cost of
using an arc (qki , qℓi+1 ) for variable-value pair hxi , vj i will be zero if vj belongs to
Vikℓ and some positive integer cost otherwise. This cost represents the penalty for
an individual violation. In the remainder of the section we will consider unit costs
but the framework also makes it possible to use varying costs, e.g. to distinguish

xi

xi

1

1

1

1

2

2

2

2

3

3

3

3

4

4

4

4

5

5

5

5

6

6

6

6

7

7

Ni

Ni+1
i=2,...,5

7

7

Ni

Ni+1
i=2,...,5

Fig. 3. Shorthand versions of Gvar (left) and Gedit (right) for the DFA of Figure
2.
between insertions and substitutions when using the edit distance. The graph on
the left at Figure 3 is a shorthand version of Gvar for the automaton of Figure 2.
Since all values in Σ are considered, the same arcs appear between consecutive
layers. What changes from one layer to the other are the Vikℓ labels.
Taking into account substitutions, common to both Hamming and edit distances, is immediate from the previous modification. It is not difficult to see that
the introduction of costs transforms a supporting path in the domain consistency
algorithm for regular into a zero-cost path in the modified graph. The cost of
a shortest path from q0 in the first layer to a member of F in the last layer
corresponds to the smallest number of variables forced to take a value outside
of their domain.
Theorem 5. A minimum-cost path from u ∈ N 1 to v ∈ N n+1 in Gvar corresponds to a solution to soft regular[var] minimizing the variable-based cost
(Hamming distance).
Just as the existence of a path through a given arc representing a variable-value
pair constituted a support for that pair in the filtering algorithm for regular,
the existence of a path whose cost doesn’t exceed max Dz constitutes a support
for that variable-value pair in a cost-based filtering algorithm for soft regular.
Theorem 6. soft regular[var](x, M, z) is domain consistent on x and bound
consistent on z if and only if
min {cost(SP(q01 , qfn+1 ))} ≤ min Dz

qf ∈F

and
min

qk ∈Q,qf ∈F

{cost(SP(q01 , qki ))+cost(SP(qℓi+1 , qfn+1 ))} ≤ max Dz ,

∀xi ∈ x, vj ∈ Di

where δ(qk , vj ) = qℓ and cost(SP(u, v)) denotes the cost of a shortest path from
u to v in Gvar .
Computing shortest paths from the initial state in the first layer to every
other node and from every node to a final state in the last layer can be done in
O(n |δ|) time3 through topological sorts because of the special structure of the
graph. That computation can also be made incremental in the same way as in
[12]. Recently, that same result was independently obtained in [3]. We however
go further by considering edit distance, for which insertions and deletions are
allowed as well.
For deletions we need to allow “wasting” a value without changing the current
state. To this effect, we add to Gvar an arc (qki , qki+1 ) ∀ 1 ≤ i ≤ n, qk ∈ Q, with
Vikk = ∅, if it isn’t already present in the graph. To allow insertions, inspired by
ǫ-transitions in DFAs, we introduce some special arcs between nodes in the same
layer: if ∃v ∈ Σ such that δ(qk , v) = qℓ then we further add an arc (qki , qℓi ) ∀ 1 ≤
i ≤ n + 1 with fixed positive cost. Figure 3 provides an example of the resulting
graph (on the right). Unfortunately, those special arcs modify the structure of
the graph since cycles (of strictly positive cost) are introduced. Consequently
shortest paths can no longer be computed through topological sorts. An efficient
implementation of Dijkstra’s algorithm increases the time complexity to O(n |δ|+
n |Q| log(n |Q|)). Regardless of this increase in computational cost, Theorems 5
and 6 can be generalized to hold for soft regular[edit] as well.

5

Aggregating Soft Constraints

The preceding sections have introduced filtering algorithms based on different
violation measures for two soft global constraints. If these filtering techniques
are to be effective, especially in the presence of soft constraints of a different
nature, they must be able to cooperate and communicate. Even though there
are many avenues for combining soft constraints, the objective almost always
remains to minimize constraint violations. We propose here a small extension
to the approach of [13], where meta-constraints on the cost variables of soft
constraints are introduced. We illustrate this approach with the newly introduced
soft gcc.
Definition 12 (Soft global cardinality aggregator). Let S be a set of soft
constraints and zi ∈ Dzi the variable indicating the violation cost of Si ∈ S. The
soft global cardinality aggregator (sgca) is defined as soft gcc[⋆](Z, l, u, zagg )
where Z = {z1 , . . . , z|S| }, li , ui is the interval defining the allowed number of
occurrences of each value in the domain of zi and zagg ∈ Dzagg ⊆ N the cost
variable based on the violation measure ⋆.
When all constraints are either satisfied or violated (Z ∈ {0, 1}|S| ) the MaxCSP approach can be easily obtained by setting l1 = 0, u1 = 0, violation(Z) =
3

|δ| refers to the number of transitions in the automaton.

P

d∈DZ overf low(Z, d) and reading the number of violations in zagg . The sgca
could also be used as in [13] to enforce homogeneity (in a soft manner) or to
define other violation measures like restricting the number of highly violated
constraint. For instance, we could wish to impose that no more then a certain
number of constraints are highly violated, but since we cannot guarantee that
this is possible the use of sgca allows to state this wish without risking to
create an inconsistent problem. More generally, by defining the values of l and
u accordingly it is possible to limit (or at least attempt to limit) the number
violated constraints by violation cost. Another approach could be to set all u
to 0 and adjust the violation function so that higher violation costs are more
penalized. The use of soft meta-constraints, when possible, is also an alternative
to the introduction of disjunctive constraints since they need not be satisfied for
the problem to be consistent.
In the original meta-constraint framework, similar behaviour can be established by applying a cost-gcc to Z. For instance, we can define for each pair (zi , d)
(d ∈ Dzi ) a cost d which penalizes higher violations
P more. With the soft gcc,
this cost function can be stated as violation(Z) = d∈DZ d·overflow(Z, d). However, as for this variant of the soft gcc we have l = 0, the soft gcc will be
much more efficient than the cost-gcc, as was discussed at the end of Section 3.
In fact, the sgca can be checked for consistency in O(nm) time and made domain
consistent in O(m)
P time (where n = |S| and m = ∪i |Dzi | whenever l = 0 and
violation(Z) = d∈DZ F (d) · overflow(Z, d) for any cost function F : DZ → R+ .

6

Conclusion

We have presented soft versions of two global constraints: the global cardinality
constraint and the regular constraint. Different violation measures have been
presented and the corresponding filtering algorithms achieving domain consistency have been introduced. These new techniques are based on the addition
of “relaxation arcs” in the underlying graph and the use of known graph algorithms. We also have proposed to extend the Meta-Constraint framework for
combining constraint violations by using the soft version of gcc.
Since these two constraints are very useful to solve Personnel Rostering Problems the next step is thus the implementation of these algorithms in order to
model such problems and benchmark these new constraints.

References
1. R.K. Ahuja, T.L. Magnanti, and J.B. Orlin. Network Flows. Prentice Hall, 1993.
2. K.R. Apt. Principles of Constraint Programming. Cambridge University Press,
2003.
3. N. Beldiceanu, M. Carlsson, and T. Petit. Deriving Filtering Algorithms from
Constraint Checkers. In Proceedings of the Tenth International Conference on
Principles and Practice of Constraint Programming (CP 2004), volume 3258 of
LNCS. Springer, 2004.

4. N. Beldiceanu and T. Petit. Cost Evaluation of Soft Global Constraints. In
CPAIOR 2004: Proceedings of the First International Conference, volume 3011
of LNCS, pages 80–95. Springer, 2004.
5. S. Bistarelli. Semirings for Soft Constraint Solving and Programming, volume 2962
of LNCS. Springer, 2004.
6. D. Dubois, H. Fargier, and H. Prade. The calculus of fuzzy restrictions as a basis
for flexible constraint satisfaction. In Proceedings of the Second IEEE International
Conference on Fuzzy Systems, volume 2, pages 1131–1136, 1993.
7. H. Fargier, J. Lang, and T. Schiex. Selecting preferred solutions in fuzzy constraint
satisfaction problems. In Proceedings of the first European Congress on Fuzzy and
Intelligent Technologies, 1993.
8. R. Freuder and M. Wallace. Partial Constraint Satisfaction. Artificial Intelligence,
58:21–70, 1992.
9. W.J. van Hoeve. A Hyper-Arc Consistency Algorithm for the Soft Alldifferent
Constraint. In Proceedings of the Tenth International Conference on Principles and
Practice of Constraint Programming (CP 2004), volume 3258 of LNCS. Springer,
2004.
10. J. Larrosa. Node and Arc Consistency in Weighted CSP. In Proceedings of
the Eighteenth National Conference on Artificial Intelligence, pages 48–53. AAAI
Press/The MIT Press, 2002.
11. J. Larrosa and T. Schiex. In the quest of the best form of local consistency for
Weighted CSP. In Proceedings of the Eighteenth International Joint Conference
on Artificial Intelligence, pages 239–244. Morgan Kaufmann, 2003.
12. G. Pesant. A Regular Language Membership Constraint for Finite Sequences of
Variables. In Proceedings of the Tenth International Conference on Principles and
Practice of Constraint Programming (CP 2004), volume 3258 of LNCS. Springer,
2004.
13. T. Petit, J.-C. Régin, and C. Bessière. Meta constraints on violations for over
constrained problems. In Proceedings of the 12th IEEE International Conference
on Tools with Artificial Intelligence (ICTAI), pages 358–365, 2000.
14. T. Petit, J.-C. Régin, and C. Bessière. Specific Filtering Algorithms for Over
Constrained Problems. In Proceedings of the Seventh International Conference on
Principles and Practice of Constraint Programming (CP 2001), volume 2239 of
LNCS, pages 451–463. Springer, 2001.
15. J.-C. Régin. Generalized Arc Consistency for Global Cardinality Constraint. In
Proceedings of AAAI/IAAI, volume 1, pages 209–215. AAAI Press/The MIT Press,
1996.
16. J.-C. Régin. Arc Consistency for Global Cardinality Constraints with Costs. In
Proceedings of the Fifth International Conference on Principles and Practice of
Constraint Programming (CP’99), volume 1713 of LNCS, pages 390–404. Springer,
1999.
17. J.-C. Régin. Cost-Based Arc Consistency for Global Cardinality Constraints. Constraints, 7:387–405, 2002.
18. T. Schiex. Possibilistic Constraint Satisfaction Problems or “How to handle soft
constraints ?”. In Proceedings of the 8th Annual Conference on Uncertainty in
Artificial Intelligence, pages 268–275. Morgan Kaufmann, 1992.
19. T. Schiex, H. Fargier, and G. Verfaillie. Valued Constraint Satisfaction Problems:
Hard and Easy Problems. In Proceedings of the Fourteenth International Joint
Conference on Artificial Intelligence, pages 631–639. Morgan Kaufmann, 1995.
20. A. Schrijver. Combinatorial Optimization - Polyhedra and Efficiency. Springer,
2003.

