Solving Finite Domain Constraint Hierarchies by Local Consistency and Tree Search

1 Introduction

The Constraint Hierarchy (CH) framework [Borning eta!., 1992] is a general framework for the specification and so­ lutions of over-constrained problems. Originating from research in interactive user-interface applications, the CH framework attracts much effort in the design of efficient solvers in the real number domain [Badros et a!., 2001; Hosobe eta!., 1996]. To extend the benefit ofthe CH frame­ work to also discrete domain applications, such as timetabling and resource allocation, the paper takes a step towards a gen­ eral and efficient finite domain CH solver, based on consis­ tency techniques and tree search.

· A more complete and detailed version of this paper can be ob­ tained from the authors.

!Part of this research has been carried out while the author was visiting the Department of Computer Science and Engineering, The Chinese University of Hong Kong, China

2 A Reformulation of Constraint Hierarchies

We formulate the CH framework [Borning et a!., 1992] (in particular in the definition of comparators and solution set) using error indicators [Bistarelli et al., 1999].

We denote an error value by~' possibly with subscripts. Let I = { ~, . . . , Dv} be a poset (partially ordered set), each element ~j of which is an error indicator. Given a constraint hierarchy H = { H 0 , ... , H n} where n is the number of non-required levels, and for all i E { 0, . .. , n}, H; = { c~ , ... , cL} with k; being the number of constraints in level i. An error indicator ~~ of a valuation B for a set of variables V is a tuple of error values such that~~= ((~9~, ... , ~8ZJ, ... , (~9~, ... ,~8~J) andVa E {0, ... ,n},Vb E {1, ... ,ka},~8~ = e(cgB) ifvm·s(cg) C V and ~8 ~ = 0 if vars(cg) ct. V. Error indicators provide a measure of the "badness" of valuations with respect to H.

The comparator predicate better in the original CH formu­ lation is redefined using a partial order, denoted by -<. We define -< to be irreflexive and transitive over T. Hence, it preserves the meaning of better. Intuitively,~~ -< (' means ~-;, is "better" than ~~ in I. In general, -< will not provide a total ordering. For convenience, we define j such that V~ 1 , (' E I,~l j ( 1 -+ (~/-< (') V (~/ = (').

We can redefine 1-b in the original formulation as a partial order -<z-b as follows. Given any two valuations Band (J', and the corresponding error indicators~~ and~: , -<l-b is defined as:

The intuitive meaning of~~ -<l-b ~: is that valuation(} is locally-better than valuation B.

Similarly, we can define g-b -< 9 -b, and its instances w­ s-b -<w-s-b, w-e-b -<w-e-b, and 1-s-b -<l-s-b respectively. Given any two valuations 6 and (J, and the corresponding error indicators~~ and ~::

Notice that by definition, all local/global comparators ignore constraints in hierarchy levels greater than or equal to l.

We are now ready to define the solution set S H of a CH H with variables V by:

The following lemma gives the monotonicity of the intro­ duced comparators, which are collectively denoted by -<better and =5better in the rest of the paper.

Lemma 1 Given any two error indicators~~ and{/'. If for all a, b we have f'~ ~ e~ . then~~ :5bet ter {/'.

Notice that the above lemma let us compare valuation for both local and global comparators (because the :5better order implies all the orders induced from any specific comparator) and for arbitrary error functions.

We also introduce the notion of a hierarchy problem which is a CH augmented with an Error Indicator Store.

Definition 1 A hierarchy problem P = (H, l H) is a con­ straint problem, where H is a CH with variables V and I H is a set containing error indicator stores ~-:,=d for all variables x E V and for all dE D(x) . Each D=d' is used for keeping an estimate of the errors of valuations involving { x f-7 d}.

Definition 2 A valuation 6 is a solution ofP = (H, IH) if (I) 6 is a solution of H and (2) {o =5better ~:=dfor all D=d E /H .

In other words, solutions of P = ( H, I H) are solutions of H which have a "worse" error than the estimates provided in I H. By the definition, the solutions of H always contain those of ( H, I IT) . Equality holds when the error estimates provided in l TT fails to "filter" out any solutions of H.

Theorem 1 Consider a CH H and the associated hierarchy problem P = (H, !H)·

• Sp C SH, and
• Sp -= SH if~~ =5better ~:=dforall(x f-7 d) E 6) and 6 E SH.

In particular, a hierarchy problem (H, !H) must share the same solution as H if all ~:=d E IH contain only the er­ ror value 0 (i.e. no error information). This fact is useful in ensuring the correctness of our local consistency algorithm and the completeness of our branch-and-bound solver later.

1 Note the similarity of [.=d in notation to (o which denotes the error indicator of a valuation 8. Here, (x=d is a store containing an estimate of the error associated with valuations containing x 1--t d.

3 Summary of the Results

The notion of constraint hierarchy k-consistency (CH-k-C), is defined using error indicators which are structures isomor­ phic to the structure of a given CH used for storing the error information of the CH problem (similar notion was defined by Bistarelli et a!. [ 1999]). In particular, we give an algo­ rithm for enforcing CH-2-C of a CH problem. While classical consistency algorithms [Mackworth, 1977] aim to reduce the size of constraint problems, our CH-2-C algorithm works by explicating error information that is originally implicit inCH problems. The space complexity of the CH-2-C algorithm is simply of 0( nvndnc) in the worst case where nc is the num­ ber of labeled constraints, n v is the number of variables, and nd is the size of the largest variable domain.

Incorporating a CH-2-C enforcement algorithm in a branch-and-bound algorithm, we obtain a general finite do­ main CH solver, which works for arbitrary comparators. Search space is pruned by utilizing the error information gen­ erated by the CH-2-C algorithm. Unlike other finite domain CH solvers, our proposed solver is applicable to arbitrary comparators.

We compare the performance of our proposed solver with generate-and-test, basic branch-and-bound, and the reified constraint approach by Lua [2000] .Experiments confirm the efficiency and robustness of our research prototype, which brings us one step towards practical finite domain CH solv­ ing.