arXiv:0905.3769v1 [cs.AI] 22 May 2009

# Multiset Ordering Constraints

Alan Frisch Dept of CS
University of York England frisch@cs.york.ac.uk

# Brahim Hnich

4C Lab University College Cork Ireland b.hnich@4c.ucc.ie

# Zeynep Kiziltan

CS Division Uppsala University Sweden zeynep@4c.ucc.ie Ian Miguel Dept of CS
University of York England ianm@cs.york.ac.uk

Toby Walsh 4C Lab University College Cork Ireland tw@4c.ucc.ie

## Abstract

We identify a new and important global (or nonbinary) constraint. This constraint ensures that the values taken by two vectors of variables, when viewed as multisets, are ordered. This constraint is useful for a number of different applications including breaking symmetry and fuzzy constraint satisfaction. We propose and implement an efficient linear time algorithm for enforcing generalised arcconsistency on such a multiset ordering constraint.

Experimental results on several problem domains show considerable promise.

1 Introduction Global (or non-binary) constraints are one of the factors central to the success of constraint programming [R´egin, 1994; R´egin, 1996; Beldiceanu, 2000]. Global constraints specify patterns that occur in many problems, and call efficient and effective constraint propagation algorithms. In this paper, we identify a new and important global constraint. This constraint ensures that the values taken by two vectors of variables, when viewed as multisets, are ordered. Such a constraint is useful in a number of domains. For example, in the progressive party problem (prob013 in csplib.org), we wish to assign a host for each guest and period. We can model this with a vector of variables for each period. Each variable is assigned the host for a particular guest. This model has unnecessary symmetry as the periods can be freely permuted.

We can break this symmetry by considering the multiset of values associated with each vector and ordering these multisets.The aim of this paper is to study such multiset ordering constraints and to develop efficient and effective techniques for enforcing them.

## 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 that specify allowed values for subsets of variables. A solution is an assignment of values to the variables satisfying the constraints. To find such solutions, we explore partial assignments enforcing a local consistency like generalized arc-consistency (GAC). A constraint is GAC iff, when a variable in the constraint is assigned a value, compatible values exist for all the other variables in the constraint. GAC
reduces to arc-consistency (AC) for binary constraints and to node-consistency (NC) for unary constraints. Finally, a constraint is bounds consistent (BC) iff, when a variable in the constraint is assigned its maximum or minimum value, there exist compatible values for all the other variables in the constraint. If a constraint c is NC, BC, AC or GAC then we write NC(c), BC(c), AC(c) or GAC(c) respectively.

We now define the multiset ordering. A multiset is an unordered list in which repetition is allowed. A multiset M is ordered smaller than another N, written M ≺m N iff either M is empty and N is not, or the largest value in M is smaller than the largest value in N, or the largest values are the same and, if we eliminate one occurrence of the largest value from both M and N, the resulting two multisets are ordered. We can weaken the ordering to include multiset equality. That is, M m N iff M = N or M ≺m N. As in the introductory example, we will often view the values taken by a vector of variables as a multiset. Given two vectors, ~x and
~y, we write a multiset ordering constraint as ~x ≤m ~y. This constraint is satisfied iff the values for the variables in the vectors, when treated as multisets, satisfy the multiset ordering. Similarly, we write a strict multiset ordering constraint as
~x <m ~y. Throughout the paper, we assume that the variables being ordered are disjoint and not repeated.

We also need the following notation. Input vectors are indexed from 0. The minimum element in the domain of xiis min(xi), and the maximum is max(xi). The floor function, floor(~x) assigns all variables in ~x to their minimum values, whilst the ceiling function, *ceil*(~x) assigns all to their maximums. The vector ~xv=d is identical to ~x except v now has the domain {d}. The function occ(~x) computes the occurrence vector associated with ~x. We index occurrence vectors in decreasing order from the maximum to the minimum value from the domains in ~x. When comparing two occurrence vectors, we assume they start with the occurrence of the same value, adding leading zeroes as necessary. Finally, ~x ≤lex ~y iff ~x is lexicographically less than or equal to ~y.