Efficient Representation of Adhoc Constraints

1 Introduction

Constraint programming is a promising technique for solving many difficult combinatorial problems. Since real-life con­ straints can be difficult to describe in symbolic expressions, or provide very weak propagation from their symbolic repre­ sentation, they are sometimes represented in the form of the sets of solutions or sets of nogoods. This adhoc represen­ tation provides strong propagation through domain (general­ ized arc) consistency techniques. However, the adhoc repre­ sentation is expensive in terms of memory and computation, when the adhoc constraint is large.

So there is interest in determining less expensive meth­ ods for building propagators for adhoc constraints [Friihwirth, 1998; Apt and Monfroy, 1999; Abdennadher and Rigotti, 2000; Bartak, 2001; Dao et al., 2002].

In this paper, we propose a new language-independent rep­ resentation for adhoc constraints, the box constraint collec­ tion. The idea is to break up an adhoc constraint into pieces and cover these pieces using box constraints as tiles. This can be done automatically with a greedy algorithm. With the aid of constructive disjunction and a suitable choice of constraint templates in the collection, our new representation achieves domain consistency.

2 Propagation Based Constraint Solving

In this section we give our terminology for constraint satis­ faction problems, and propagation based constraint solving.

An integer valuation B is a mapping of variables to integer values, written {x1 >--+ dJ, ... ,xn >--+ dn}· We extend the valuation B to map expressions and constraints involving the variables in the natural way. We sometimes treat a valuation B = { x1 >--+ d1, ... , Xn >--+ dn} as the constraint x1 = d1 !\ .. . !\ Xn = dn. Let vars be the function that returns the set of (free) variables appearing in a constraint or valuation.

A domain D is a complete mapping from a fixed (count­ able) set of variables V to finite sets of integers. A domain D1 is stronger than a domain D2, written D1 ~ D2, if D1 (x) ~ D2 (x) for all variables x.

·we thank the anonymous referees for their constructive com­ ments. The work described in this paper was substantially supported by a grant from the Research Grants Council of the Hong Kong Spe­ cial Administrative Region (Project no. CUHK4183/00E).

Peter J. Stuckey Dept. of Comp. Sci. & Soft. Eng. University of Melbourne, Australia

pjs®cs.mu.oz.au

In an abuse of notation, we define a valuation B to be an element of a (non-false) domain D, written B E D, ifB(x;) E D(x;) for all x; E vars(B).

We are also interested in the notion of an initial domain, denoted by D;nit · The initial domain gives the initial values possible for each variable.

A constraint c over variables x1 , · .· , xn, written as c(x1, .. . , xn), restricts the values that e.ach variable x; ca.n take simultaneously. An adhoc constramt c(x1, ... , xn) 1s defined extensionally as a set of valuations B over the vari· abies x1, . .. , Xn. We say B. E c is a solution of c. For any valuation B on variables x1, ... , Xn, with B fl. c, we call B a nogood of c.

Often we define constraints intensionally using some well understood mathematical syntax. For an intensionally defined constraintcwehavethatB E ciffvars(B) = vars(c)!\Z Fe c. Forexampletheconstraintx1 = x2+l whereDinit(xl) = D;nit(x2 ) = {1 , 2, 3} defines the set of solutions {{ :r1 f-t 2,x2 >--+ l},{xl >--+ 3,x2 >--+ 2}}.

A constraint satisfaction problem (CSP) [Tsang, 1993], consists of a set of constraints c1, ... , ck over a set of vari· abies x1 , . . . , xn, where each variable x; can only take values from its domain D;nit(x;), a set of integers. Solving a CSP requires finding a value for each variable from its domain so that no constraint is violated, i.e. all constraints are satisfied.

A propagator f is a monotonically decreasing function from domains to domains. The generalized arc consistent propagator for a constraint cis defined as dom(c)(D)(x) = {B(x) I B E D !\ B E c} where x E vars(c), otherwise dom(c)(D)(x) = D(x) . A propagation solver for prop~· gators F repeatedly applies propagators f E F to a domam D until no further change in D results.

3 Box Constraint Collections

Adhoc constraints are usually implemented as tabled con· straints by listing all the solutions or no goods, incurring space and time overhead. Often we represent a constraint in an ad· hoc manner because it is difficult (or unwieldy) to describe it using a symbolic expression. However, it may be easier to find symbolic expressions if we examine part of the so· lution space. Therefore, we propose representing an adhoc constraint Cadhoc with a set of simple constraints in DNF.

A box B = Il7= 1 [a; .. b;] is ann-dimensional hyper-cube, where [a; .. b;] is a (closed) interval of integers a; and b;. If c(x1 , . .. ,xn) is a constraint on variables xl, ... ,xn, then A7=l a;j ::; Xj ::; b;j 1\ c(x1, ... , xn) is a box constraint, which we write as B => c. We restrict the form of constraints c(x1 , .. . , xn) to certain templates. A box constraint collec­ tion (BCC) is simply a disjunction of box constraints.

The idea is thus to use box constraints in a collection as "ti les" to cover the solution space of an adhoc constraint. The template defining c in a box constraint B => c determines the shape of the tile. Triangles and rectangular boxes are good tile shapes for filling grids. If cis true, then B => c is simply the box B. If cis of the form LJ=l ajXj ::; a0, then we call B => c a triangle.

Lemma 1 Let

and suppose each constraint c; is implemented by a gener­ alized arc consistent propagator, then using constructive dis­ junction on this representation achieves generalized arc con­ sistency for Cadhoc·

Example 1 A box constraint collection representation of the constraint Ctri shown in Figure 1 is

Due to space limitation, we cannot show how box con­ straint collections can be compiled into indexicals directly and efficiently.

4 Experiments

We compare the propagation efficiency among box (indexi­ cal BCCs for boxes only), tri- box (indexical BCCs for trian­ gles and boxes) and rel (the built-in relation/3 for binary adhoc constraints) on randomly generated cubic inequalities of the form d1X 3 + d2X 2 Y + d3XY 2 + d4Y 3 + d5X 2 + d6XY + d7 Y 2 + d8X + d9 Y < d10 . The coefficients are ran­ domly chosen between [-9 .. 9]. The domain size is 100. For each variable X andY, we repeat M times picking a subset S ~ D;nit(x) where lSI = W, and adding the constraints x -::j:. v for each v E S. These constraint additions are then re­ moved and the next set S picked. We do our implementation with SICStus Prolog 3.9.1 on a Sun Blade 1000 workstation.

Table 1 summarizes some results. N is the number of solutions. B and T are the number of boxes and triangles. tri-box generates no boxes (B = 0) in all 3 instances. gen is the generation time. rel and prop (for box and t ri- box) are the time they spend on the propagation test M = 5000 and W = 30. tri-box is the fastest because it compactly rep­ resents the non-linear constraints with 1 or 2 triangles. box, although is faster than rel, it takes a long time to generate be­ cause every box covers only a few solutions, and many boxes are needed.

I

5 Conclusion

We have proposed a new language-independent representa­ tion, box constraint collection, for adhoc constraints. With constructive disjunction, our new representation achieves generalized arc consistency, if all constraints inside the col­ lection do.

Future work includes improving the current greedy BCC generation algorithm, and optimizing the indexicals of a box constraint collection.