TECHNICAL REPORT
`TECHNICAL REPORT
`R-121-Al
`R-121-AI
`
` ANell
`
`ELSEVIER
`
`
`
`Artificial
`Intelligence
`Artificial Intelligence 68 (1994) 211-241
`
`Experimental evaluation of preprocessing algorithms for
`constraint satisfaction problems
`
`Rina Dechter*’*, Itay Meiri”
`“Information and Computer Science Department, University of California, Irvine, CA 29717-3425,
`USA
`Cognitive Systems Laboratory, Computer Science Department, University of California,
`Los Angeles, CA 90024, USA
`
`Received February 1992; revised July 1993
`
`Abstract
`
`This paper presents an experimental evaluation of two orthogonal schemes for pre-
`processing constraint satisfaction problems (CSPs). The first of these schemes involves a
`class of local consistency techniques that includes directional arc consistency, directional
`path consistency, and adaptive consistency. The other scheme concerns the prearrangement
`of variables in a linear order to facilitate an efficient search.
`In the first series of
`experiments, we evaluated the effect of each of the local consistency techniques on
`backtracking and backjumping. Surprisingly, although adaptive consistency has the best
`worst-case complexity bounds, we have found that it exhibits the worst performance,
`unless the constraint graph was very sparse. Directional arc consistency (followed by either
`backjumping or backtracking) and backjumping (without any preprocessing) outperformed
`all other techniques: moreover,
`the former dominated the latter in computationally
`intensive situations. The second series of experiments suggests that maximum cardinality
`and minimum width are the best preordering (i.e., static ordering) strategies, while
`dynamic search rearrangementis superior to all the preorderings studied.
`
`1. Introduction
`
`Constraint satisfaction tasks belong to the class of NP-complete problems and,
`as such, normally lack realistic measures of performance. Worst-case analysis,
`because it depends on extreme cases, may yield an erroneous view of typical
`performance of algorithms used in practice. Average-case analysis, on the other
`
`* Corresponding author. E-mail: dechter@ics.uci.edu.
`
`0004-3702/94/$07.00 © 1994 Elsevier Science BV. All rights reserved
`SSDI 0004-3702(93)E0057-S
`
`1
`
`CONFIGIT 1047
`
`CONFIGIT 1047
`
`1
`
`

`

`212
`
`R. Dechter, 1. Meiri
`
`{ Artificial Intelligence 68 (1994) 211-24]
`
`is extremely difficult and is highly sensitive to simplifying theoretical
`hand,
`assumptions. Thus, theoretical analysis must be supplemented by experimental
`studies.
`The most thorough experimental studies reported so far include Gaschnig’s
`comparisons of backjumping, backmarking and constraint propagation [12],
`Haralick and Elliot’s study of look-ahead strategies [14], Brown and Purdom’s
`experiments with dynamic variable orderings
`[21,22], and, more recently,
`Dechter’s experiments with structure-based techniques [3], and Prosser’s hybrid
`tests with backjumping and forward-checking strategies [20]. Additional studies
`were reported in [6, 13, 23, 26, 27}.
`Experimental studies are most informative when conducted on a “‘representa-
`tive” set of problems from one’s own domain of application. However, this is very
`difficult to effect. Real-life problems are often too large or too ill-defined to suit a
`laboratory manipulation. A common compromise is to use either randomly
`generated problems or canonical examples (e.g., n-queens, crossword puzzles,
`and graph-coloring problems). Clearly, conclusions drawn from such experiments
`reflect only on problem domains that resemble the experimental conditions and
`caution must be exercised when generalizing to real-life problems. Such experi-
`ments do reveal
`the crucial parameters of a problem domain, and so help
`establish the relative usefulness of various algorithms.
`Our focus in this paper is on algorithms whose performance, as revealed by
`worst-case analysis, is dependent on the topological structure of the problem. Our
`aim is to uncover whether the same dependency is observed empirically and to
`investigate the extent to which worst-case bounds predict actual performance.
`Our primary concern is with preprocessing algorithms and their effect on
`backtracking’s performance. Since our preprocessing algorithms are dependent on
`a static ordering of the variables they invite different heuristics for variable
`ordering. We tested the effect of such orderings on the preprocessing algorithms
`as well as on regular backtracking and backjumping.
`Weorganized our experimental results into two classes. The first class concerns
`consistency enforcing algorithms, which transform a given constraint network into
`a more explicit representation. On this more explicit representation, any back-
`tracking algorithm is guaranteed to encounter fewer deadends [16]. Since these
`algorithms are polynomial while backtracking is exponential, and since they
`always improve search, one may hastily conclude that they should always be
`exercised. Our aim was to test this hypothesis. The three consistency enforcing
`algorithms tested are directional arc consistency (DAC), directional path consis-
`tency (DPC), and adaptive consistency (ADAPT) [6]. These algorithms represent
`increasing levels of preprocessing effort as well as an increasing improvement in
`subsequent search. Although DAC and DPC, whose complexities are quadratic
`and cubic, respectively, can still be followed by exponential search (in the worst
`case), ADAPT is guaranteedto yield a solution in time bounded by O(exp(W*)),
`where W* is a parameterreflecting the sparseness of the network.
`Ourresults show, contrary to predictions based on worst-case analysis, that the
`average complexity of backtracking on our randomly generated problemsis far
`
`2
`
`

`

`R. Dechter, I. Meiri
`
`/ Artificial Intelligence 68 (1994) 211-241
`
`213
`
`from exponential. Indeed the preprocessing performed by the most aggressive
`scheme, ADAPT,did not pay off unless the graph was very sparse, in spite ofits
`theoretical superiority to backtracking. On the other hand, the least aggressive
`scheme, DAC, came out as a winner
`in computationally intensive cases.
`Apparently, DAC performsjust the desired amount of preprocessing. Additional-
`ly, while ADAPT showedthatits average complexity is exponentially dependent
`on W*, the dependence of all other schemes on W* seems to be quite weak or
`even non-existent.
`In the second class we report the effect of various static ordering strategies on
`backtracking and backjumping without preprocessing. Static orderings, in contrast
`to dynamic orderings, are appealing in that they do not require any overhead
`during search. We tested four static heuristic orderings, minimum width (MIN),
`maximum degree (DEG), maximum cardinality (CARD), and depth-first search
`(DFS). Those orderings are advised when analyzing their effect on the preproces-
`sing algorithms ADAPT and even DPCas they yield a low W*. Although no
`worst-case complexity ties backtracking or backjumping to W*, we nevertheless
`wanted to discover whether a correlation exists, and which of these static
`orderings yields a better average search. Lastly, in order to relate our experiments
`with other experiments reported in the literature, we compared ourstatic
`ordering with one dynamic ordering, dynamic search rearrangement (DSR) [21].
`Wetested two implementation styles of DSR, presenting a tradeoff between space
`and time overhead.
`Our
`results show that minimum width and maximum cardinality clearly
`dominated the maximum degree and depth-first search orderings. However, the
`exact relationship between the first two is still unclear. While dynamic ordering
`was only second or third best when implemented in a brute-force way it
`outperformed all static orderings when a more careful
`implementation that
`restricted its time overhead was introduced.
`The remainder of the paper is organized as follows: we review the constraint
`network model and general background in Section 2, present the tested algo-
`rithms in Section 3, describe the experimental design in Section 4, discuss the
`results in Section 5, and provide a summary and concluding remarksin Section 6.
`
`2. Constraint processing techniques
`
`A constraint network (CN) consists of a set of variables X = {X,,...,X,},
`each associated with a domain of discrete values D,,...,D,, and a set of
`constraints {C,,...,C,}. Each constraint is a relation defined on a subset of
`variables. The tuples of this relation are all the simultaneous value assignments to
`this variable subset which, as far as this constraint alone is concerned,arelegal.’
`
`‘This does not meanthat the actual representation of any constraint is necessarily in the form ofits
`defining relation, rather the relation can in principle be generated using the constraint’s specification
`without the need to consult other constraints in the network.
`
`3
`
`

`

`214
`
`R. Dechter, I. Meiri
`
`/ Artificial Intelligence 68 (1994) 211-241
`
`Formally, constraint C, has two parts: a subset of variables S;= {X;,... X}
`on which it is defined, called a constraint-subset, and a relation vel, defined over
`S;: rel, CD, X +++ x dD, The scheme of a CNis the set of its constraint subsets,
`namely, scheme(CN) = {S,,5S,,...,5,}, $;¢X. An assignment of a unique
`domain value to each memberof some subset of variables is an instantiation. An
`instantiation is a solution only if it satisfies all the constraints. The set of all
`solutions is a relation p defined on the set of all variables. Formally,
`
`p= {(X,=x,,...,X, =x,)| VS, E scheme, I;p Crel;} ,
`
`(1)
`
`whereII,is the projection ofrelation p over a subset of its variables X, namely
`it is the set of all subtuples over X that can be extended to a full tuple in p.
`A CN may beassociated with a constraint graph in which nodes represent
`variables and arcs connect variables that appear in the same constraint. For
`example,
`the CN depicted in Fig. 1(a) represents a crossword puzzle. The
`variables are E, D, C, A, and B. The scheme is {ED, EC, CA, AD, DB}. For
`instance, the pair DE is in the scheme since the word associated with D and the
`word associated with E share a letter. The constraint graph is given in Fig. 1(b).
`Typical tasks defined on a CN are determining whetherasolution exists, finding
`one solution or the set ofall solutions, and establishing whether an instantiation
`of a subset of variables is part of a global solution. Collectively, these tasks are
`known as constraint satisfaction problems (CSPs).
`
`
`
`Dr= {hoses, laser, sheet ,snail,steer}
`Da=Dp = {hike,aron,keet,earn, same}
`De = {run,sun,let ,yes,eat ,ten}
`Dz = {no,de,us,it}
`
`Cap = {(hoses,same) , (laser, same) , (sheet,earn),
`(snail,aron),(steer,earn)}
`
`(a)
`
`(c)
`(b)
`Fig. 1. (a) A crossword puzzle (D denotes domains of variables, C,, is the constraint between
`variables A and B), (b) its CN representation, and (c) a depth-first search preordering.
`
`4
`
`

`

`R. Dechter, I. Meiri
`
`/ Artificial Intelligence 68 (1994) 211-241
`
`215
`
`Techniques used in processing constraint networks can beclassified into three
`categories: (1) search algorithms, for systematic exploration of the space ofall
`solutions, which all have backtracking as their basis; (2) consistency enforcing
`algorithms,
`that enforce consistency on small parts of the network, and (3)
`structure-driven algorithms, which exploit the topological features of the network
`to guide the search. Hybrids of these techniques are also available. For a detailed
`survey of constraint processing techniques, see [4, 15].
`Backtracking traverses the search space in a depth-first fashion. The algorithm
`typically considers the variables in some order. It systematically assigns values to
`variables until either a solution is found or the algorithm reaches a deadend,
`wherea variable has no value consistent with previous assignments. In this case
`the algorithm backtracks to the most recent instantiation, changes the assigned
`value, and continues.
`It
`is well known that
`the worst-case running time of
`backtracking is exponential.
`Improving the efficiency of backtracking amounts to reducing the size of the
`search space it expands. Two types of procedures were developed: preprocessing
`algorithms that are employed prior to performing the search, and dynamic
`algorithms that are used during the search.
`The preprocessing algorithms include a variety of consistency enforcing algo-
`rithms [9, 16, 18]. These algorithms transform a given CN into an equivalent, yet
`more explicit form, by deducing new constraints to be added to the network.
`Essentially, a consistency enforcing algorithm makes a small subnetwork con-
`sistent relative to its surrounding constraints. For example,
`the most basic
`consistency algorithm, called arc consistency or 2-consistency (also known as
`constraint propagation or constraint relaxation), ensures that any legal value in
`the domain of a single variable has a legal match in the domain of any other
`variable. Path consistency (or 3-consistency) ensures that any consistent solution
`to a two-variable subnetwork is extensible to any third variable, and, in general,
`i-consistency algorithms guarantee that any locally consistent instantiation of i — 1
`variables is extensible to any ith variable. The algorithms, DAC, DPC, and
`ADAPTareall restricted (because they take into account the direction in which
`backtracking instantiates the variables) versions of these consistency enforcing
`algorithms.
`The preprocessing algorithmsalso include algorithms for ordering the variables
`prior to search. Several heuristics for static orderings have been proposed [7, 10].
`The heuristics used in this paper—minimum width, maximum cardinality, maxi-
`mum degree, and depth-first search—follow the intuition that tightly constrained
`variables should be instantiated first.
`Strategies that dynamically improve the pruning power of backtracking can be
`classified as either look-ahead schemesor look-back schemes. Look-ahead schemes
`are invoked whenever the algorithm is about
`to assign a value to the next
`variable. Some schemes, such as forward-checking, use constraint propagation
`[14, 28]
`to predict the way in which the current instantiation restricts future
`assignments of values to variables. An example of a look-ahead schemeis
`dynamic search rearrangement, which decides what variable to instantiate next
`
`5
`
`

`

`216
`
`R. Dechter, 1. Meiri
`
`| Artificial Intelligence 68 (1994) 211-241
`
`{10, 21, 26}. Look-back schemes are invoked when the algorithm encounters a
`deadend and prepares to backtrack. An example of such a schemeis backjumping
`[12]. By analyzing the reasons for the deadendit is often possible to go back
`directly to the source of failure instead of to the immediate predecessor in the
`ordering. The algorithm may also record the reasons for the deadendso that the
`same conflicts will not arise again later in the search (terms used to describe this
`idea are constraint
`recording and no-good constraints). Dependency-directed
`backtracking incorporates both backjumping and no-good recording {3, 25].
`Structure-based techniques,
`such as graph-based back-jumping directional
`i-consistency, adaptive consistency, and cycle-cutset scheme can be viewed as
`structure-based improvements of some of the above techniques[4].
`
`3. The tested algorithms
`
`Wefirst present our two search algorithms, backtracking and backjumping, and
`then describe the consistency enforcing algorithms and the ordering heuristics we
`used.
`
`3.1. Backtracking and backjumping
`
`A backtracking algorithm for finding one solution is given in Fig. 2. It is defined
`by two recursive procedures, forward and go-back. The first extends a current
`partial assignment if possible, and the second handles deadend situations. The
`procedures maintain lists of candidate values, C,, for each variable, X,. Their
`initial values are computed by compute-candidates(x,,... , x;, X;.,), which selects
`all values in the domain of variable X,,,
`that are consistent with previous
`assignments. Backtracking starts by calling forward with i=0, namely,
`the
`instantiated list is empty.
`Backjumping improves the go-back phase of backtracking. Whenever a
`deadendoccurs at variable X, it backs up to the most recent variable Y connected
`to X in the constraint graph. If variable Y has no morevalues, then it should back
`up more, to the most recent variable Z connected to both X and Y, and so on.
`This algorithm is a graph-based variant of Gaschnig’s backjumping [12] which
`extracts knowledge about dependencies from the constraint graph alone. Graph-
`based backjumping has been shown to outperform backtracking on an instance-
`by-instance basis [3]. For simplicity, backjumping refers to graph-based bac-
`kjumping throughout the remainder of this paper.
`In our implementation of backjumping, both forward and jump-back (the
`go-back variant of backjumping) carry a parameter P,
`that stores the set of
`variables that need to be consulted upon the next deadend (see Fig. 3).
`Accordingly, lines 6 and 8 of forward are changed to forward(x,,...,X;,X;4,,P)
`and jump-back(x,,...,x;,X;,,, P). Procedure jump-back is shown in Fig. 3. Its
`parameters are the partial instantiation x,,...,x,, the deadend variable X;,,,,
`and P.
`
`6
`
`

`

`R. Dechter, I. Meiri
`
`/ Artificial Intelligence 68 (1994) 211-241
`
`217
`
`
`
`forward(x,,...,X;)
`Begin
`if i=n, exit with the current assignment
`. C,,, —compute-candidates(x,,.. . ,X;,Xi41)
`if C;,, is not empty then
`X;4, <first element in C,,,, and
`remove x,,, from C;,,, and
`forward(x,, ... , XisXj41)
`. Else
`go-back(x,,...,X;)
`
`SNIAMPYND
`
`End
`
`go-back(x,,...,%;)
`Begin
`1.
`if i=0, exit (no solution exists)
`2.
`if C, is not empty then
`3.
`x,<first in C,, and
`4.
`remove x, from C,, and
`5.
`forward(x,,...,%;)
`6. Else
`7.
` go-back(x,,...,X;_1)
`End
`
`
`Fig. 2. Algorithm backtracking.
`
`jump-back(x,,... ,X;,; X41, P)
`Begin
`if i=0, exit (no solution exists)
`1.
`2. PARENTS < Parents’(X,,,)
`3. P<—PU PARENTS
`4. Let j be the largest indexed variable in P,
`5S. P<—P-X,
`6.
`if C, # then
`7
`x; = first in C,;, and
`8
`remove x, from C;, and
`9.
` forward(x,,...,x;, P)
`10. Else
`11.
`jump-back(x,,..., X;-1, X;, P)
`End
`
`
`Fig. 3. Procedure jump-back.
`
`? Parents(X,) are those variables connected to X, that precede X, in the ordering.
`
`7
`
`

`

`218
`
`R. Dechter, I. Meiri
`
`/ Artificial Intelligence 68 (1994) 211-241
`
`Consider, for instance, the ordered constraint graph in Fig. 1(a). If the searchis
`performed in the order E, D, A, C, B, and a deadend occurs at B, the algorithm
`will jump back to variable D since B is not connected to either C or A.
`In general, the implementation of backjumping requires careful maintenance of
`each variable’s parent set. Some orderings, however, facilitate a simple im-
`plementation. If we perform a depth-first search (DFS) on the constraint graph (to
`generate a DFStree) and apply backjumping along the resulting DFS numbering
`[8], finding the jump-back destination amounts to going back to the parent of X in
`the DFS tree. A DFS tree of the graph in Fig. 1(b) is given in Fig.
`l(c). The
`directed arcs are part of the DFS tree. Therest of the arcs are undirected[8]. The
`DFSordering (which amountsto an in-ordertraversal of this tree) is (E, D, B, A,
`C). Again, if a deadend occurs at node A, the algorithm retreats to its parent in
`the DFS tree, D. When backjumping is performed along a DFS ordering of the
`variables,
`its complexity can be bounded by O(exp(m)) steps, where m is the
`depth of the DFS tree [2].
`The backjumping procedure we use here is relatively conservative in that
`variables are eliminated from the parent set only when they are jumped back to
`(see step 5 of jump-back). This may result
`in deterioration of performance
`however. Asthe size of the parent set gets larger, backjumping will have less
`opportunities to execute big jumps back, and its performance will converge into
`that of naive backtracking. This can be corrected by a more sophisticated “parent
`releasing” method. One approach is to index each variable with the trigger
`variable that introduced it to the parent set, and releasing it upon processing that
`trigger variable by forward. For a discussion of several such improvements of
`backjumping see [11, 20].
`
`3.2. Local consistency algorithms
`
`Deciding the consistency level that should be enforced on the network is not a
`clear-cut choice. Generally, backtracking will benefit from representations that
`are as explicit (therefore of a higher consistency level) as possible. However, the
`complexity of enforcing i-consistency is exponential in i (and may also require
`exponential memory). Thus,
`there is a tradeoff between the effort spent on
`preprocessing and that spent on search. The primary goal of our paper is to
`uncoverthis tradeoff.
`Algorithms DAC, DPC, and ADAPT, being the directional versions of arc
`consistency, path consistency and n-consistency, respectively, have the advantage
`that they take into account the direction in which backtracking will eventually
`search the problem. Thus, they avoid processing many constraints that are not
`encountered during search.
`Westart with ADAPT, then generalize its underlying principle to describe a
`class of preprocessing algorithms that contains both DAC and DPC. Given an
`ordering of the variables, the parent set of a variable X is the set of all variables
`connected to X (in the constraint graph) that precede X in the ordering. The
`width of a node is the size of its parent set. The width of an ordering is the
`maximum width of nodesin that ordering, and the width of a graph is the minimal
`
`8
`
`

`

`R. Dechter, I. Meiri / Artificial Intelligence 68 (1994) 211-241
`
`219
`
`B
`
`A
`
`C
`
`D
`
`E
`
`B
`
`A
`
`Cc
`
`D
`
`E
`
`(a)
`
`(b)
`
`Fig. 4. Ordered constraint graphs.
`
`width ofall its orderings. For instance, given the ordering (E, D, C, A, B) in Fig.
`4(a), the width of node B is 1, while the width of this ordering is 2 (since the
`width of A is 2 and there is no node having a larger width). Since there is no
`width-1 ordering, the width of this graph is 2. Algorithm ADAPT, shownin Fig.
`5, processes the nodes in a reverse order, that is, each node is processed before
`any ofits parents.
`The procedure record-constraint(X, SET) generates and records those tuples of
`variables in SET that are consistent with at least one value of X. For instance, in
`our example, if A has only one feasible word, aron, in its domain and C and D
`each havetheir initial domains, then the call for record-constraint(A, {C, D}) will
`result in recording a constraint on the variables {C, D}, allowing only the pairs
`{(earn, run), (earn, sun), (earn, ten)}. ADAPT maytighten existing constraints as
`well as impose constraints over new clusters of variables. It has been shown [6]
`that, when the procedure terminates, backtracking can solve the problem, in the
`
`ADAPT(X,,..., Xn)
`Begin
`1. fori=n to 1 by —1 do
`2.
`compute parents(X,)
`3.
`perform record-constraint(X,, parents(X;))
`4.
`in the
`constraint graph,
`connect
`all unconnected elements
`parents(X;,)
`
`End
`
`in
`
`Fig. 5. Algorithm ADAPT.
`
`9
`
`

`

`220
`
`R. Dechter, I. Meiri
`
`/ Artificial Intelligence 68 (1994) 211-241
`
`order prescribed, without encountering any deadend. The topology of the new
`induced graph can be found prior to executing the procedure by recursively
`connecting in the graph any two parents sharing a commonsuccessor .
`Consider Fig. 4(a). Variable B is chosen first, and since it has only one parent,
`D,
`the algorithm records a unary constraint on D’s domain. Variable A is
`processed next, and a binary constraint is enforced on its two parents, D and C,
`eliminating all pairs that have no common consistent match in A. This operation
`may require that an arc be added between C and D. Theresulting induced graph
`contains the dashed arc in Fig. 4(b).
`Let W(d) be the width of the ordering d, and W*(d) be the width of the
`induced graph along this ordering. It can be shown that solving the problem along
`the ordering d, using ADAPT is O(n-exp(W*(d) + 1)) [6].
`The directional algorithms DAC, DPC, and directional i-consistency differ from
`ADAPTonly in the amountandsize of constraint recording performed in Step 3.
`Namely, instead of recording one constraint amongall parents, they record a few
`smaller constraints on subsets of the parents. Let Jevel be a parameter indicating
`the utmost cardinality of the recorded constraints. The class of algorithms
`adaptive(level) is described in Fig. 6. It uses a procedure, new-record(level, var,
`set), that records only constraints of size level from subsets of set.
`Adpative(level = 1) reduces to DAC, while for level = 2 it becomes DPC. The
`graph inducedbyall these algorithms (excluding the case of level = 1, where the
`graph does not change) has the same structure as the one generated by ADAPT.
`Since adaptive(level = W*(d)) is the same as ADAPT,it is guaranteed to generate
`a backtrack-free solution.
`
`adaptive(level, X,,...,X,)
`Begin
`1.
`2.
`3.
`4.
`End
`
`fori=n to 1 by —1 do
`compute parents(X;)
`perform new-record(level, X,, parents(X,))
`for level = 2, connect in the graph all elements in parents(X,)
`
`new-record(level, var, set)
`Begin
`1.
`if level <|set| then
`2.
`for every subset S in set, subject to |S| = level do
`3.
`record-constraint(var, S)
`4.
`end
`5. else do record-constraint(var, set)
`End
`
`
`
`Fig. 6. Procedures adaptive and new-record.
`
`10
`
`10
`
`

`

`R. Dechter, I. Meiri
`
`/ Artificial Intelligence 68 (1994) 211-241
`
`221
`
`The complexity of adaptive(level) is both time- and space-dominated by the
`procedure new-record(level) which is
`
`o((",) . (grintieveriedy)
`
`level
`
`k being the maximal domain size. Clearly, the bound can be tightened if the
`ordering d results in a smaller W*(d). However, finding the ordering that has the
`minimum induced width is an NP-complete problem [1].
`
`3.3. Preordering of variables
`
`It is well known that the ordering of variables, whether static throughout search
`or dynamic, may have a tremendous impact on the size of the search space
`explored by backtracking algorithms. Finding an ordering that minimizes the
`search space is difficult and consequently researchers have concentrated on
`devising heuristics for variable ordering.
`Weconsider four static orderings. The minimum width (MIN) heuristic [10]
`orders the variables from last to first by selecting, at each stage, a node having a
`minimal degree in the subgraph restricted to all nodes not yet selected. (The
`degree of a node in a graph is the numberofits adjacent nodes.) As its name
`indicates,
`the heuristic results in a minimum width ordering. The maximum
`degree (DEG) heuristic orders the variables in a decreasing order of their degree
`in the constraint graph. This heuristic also aims at (but does not guarantee)
`finding a minimum width ordering. The maximum cardinality (CARD) ordering
`selects the first variable arbitrarily, then, at each stage, selects the variable thatis
`connected to the largest set of already selected variables. A depth-first search
`ordering (DFS) is generated by a DFS traversal of the constraint graph. It can be
`combined with any of the previous orderings to create a tie-breaking rule. In our
`experiments, the tie-breaking rule was random.
`The best known dynamic ordering is the dynamic search rearrangement (DSR),
`which was investigated analytically via average-case analysis in [14, 19,21], and
`experimentally in {23, 24,26]. This heuristic selects as the next variable to be
`instantiated a variable that has a minimal number of values that are consistent
`with the current partial solution. Heuristically,
`the choice of such a variable
`minimizes the remaining search. Other, more elaborate estimates of the remain-
`ing search space were also considered [1, 29].
`
`4. Experimental design
`
`Our experiments were performed at two different locations, site-1 and site-2.
`They were conducted completely independently using different implementations
`of algorithms, different
`test
`instances, and different algorithm combinations.
`Overall, 42 algorithm combinations were tested. At site-1, we executed backtrack-
`ing (BTK) and backjumping (BJ) on each problem instance twice, once directly
`
`11
`
`11
`
`

`

`222
`
`R. Dechter, I. Meiri
`
`| Artificial Intelligence 68 (1994) 211-241
`
`without any preprocessing and once after preprocessing the network by either
`DAC, DPC, or ADAPT (8 combinations). We ran each algorithm combination
`along with each one of the static orderings DEG, CARD, and MIN (24
`combinations). Two more runs, of backtracking and backjumping using DSR
`ordering, were also performed. Atsite-2 we studied only the effect of ordering
`strategies, with and without preprocessing by arc consistency.
`In this case we
`executed backtracking and backjumping on each problem instance twice, once
`without any preprocessing and once after preprocessing by DAC (4 combina-
`tions). Each algorithm combination was tested with the static orderings CARD,
`MIN, DFS, and with the DSR (16 combinations).
`Table 1 summarizes the algorithm combinations tested and their corresponding
`sites. For instance, we see that DPC-BJ (i.e., DPC followed by backjumping)
`wastested only at site-1, while BJ was tested at both site-1 and site-2. Note that
`an instance-by-instance comparison is feasible only withinsites.
`The test problems at each site were generated using the same random model,
`but with different parameters. The generator used four parameters: n,
`the
`numberof variables; k, the number of values; and p, and p,. The parameter p,
`denotes the probability that a given pair of variables will not be constrained (and
`thus will not have an arc in the constraint graph), while p, is the probability that a
`given pair of values won’t be allowed by a given constraint. In other words, the
`generator created a random graph uniformly using probability p, and then
`created a relation for each arc in the graph using probability p, (p,
`is the
`probability of a no-good). This
`random model has been used by others
`[3,12,14]° The problem instances on which we reported were not selected
`uniformly from a given distribution. Our aim was to select a subset of problems
`that appear to be more difficult. We first determined values for p, and p, that
`gave rise to relatively difficult instances, while producing sparse graphs. Then,
`from those distributions we hand-picked only the harder instances. Difficulty was
`determined by the number of deadends encountered when running backtracking
`on a DEG ordering of the instance; if the number of deadends acceded a certain
`
`Table 1
`
`Algorithms and test combinations (1—-site-1, 2—site-2).
`ADAPT
`DPC
`DAC
`BTK
`BJ
`DAC
`DPC
`ADAPT
`
`
`
`
` BJ BJ BJ BTK BTK BTK
`
`
`DEG
`
`CARD
`
`MIN
`
`1
`
`1
`2
`
`1
`2
`
`1
`
`1
`2
`
`1
`2
`
`1
`
`1
`2
`
`1
`2
`
`1
`
`1
`
`1
`
`1
`
`1
`
`1
`
`1
`
`1
`2
`
`1
`2
`
`1
`
`1
`
`1
`
`1
`
`1
`
`1
`
`DSR
`
`1
`1
`2
`2
`2
`2
`
`
`
`2 2 2DFS 2
`
`3
`“ge
`.
`.
`.
`Additional, more recently used random models are discussed in the conclusion.
`
`12
`
`12
`
`

`

`R. Dechter, I. Meiri / Artificial Intelligence 68 (1994) 211-241
`
`223
`
`Table 2
`
`Parameters of problem instances at site-1
`w*
`#
`Parameters
`
`10,
`
`consistent
`
`10,
`inconsistent
`
`15,
`consistent
`
`15,
`
`inconsistent
`
`1
`
`2
`
`3
`
`4
`
`2
`3
`
`4
`
`2
`
`3
`
`4
`
`5
`
`2
`
`3
`
`4
`
`5
`
`5
`
`17
`
`15
`
`5
`
`5
`14
`
`6
`
`11
`
`9
`
`9
`
`6
`
`3
`
`17
`
`16
`
`3
`
`{(80,70) (80,73) (80,73) (80,75) (80,77)}
`
`{(65,65) (68,55) (68,58) (68,65) (70,63) (70,65) (70,67) (75,60) (75,63)
`(75,63) (75,65) (80,60) (80,60) (80,70) (85,70) (85,70) (85,70)}
`
`{(63,55) (63,55) (65,55)(65,58) (68,55) (68,58) (68,58) (68,65) (70,60)
`(70,60) (70,60) (70,63) (70,63) (73,58) (73,58)}
`
`{(60,50) (63,50) (63,50) (65,58) (68,50)}
`
`{(75,65) (80,70) (80,75) (80,75) (80,77)}
`{(65,65) (68,60) (68,65) (70,65) (70,65) (70,67) (70,67) (73,58) (75,60)
`(75,60) (75,63) (75,65) (80,73) (80,77)}
`
`{(65,55) (65,58) (65,55) (65,68) (68,55) (68,60)}
`
`(79,61) (81,62) (84,62) (84,61) (85,63) (85,66) (85,70) (87,64) (88,72)
`(88,75) (88,75)
`
`(77,56) (78,59) (79,56) (80,59) (80,59) (81,62) (83,61)
`(85,68) (86,63)
`
`(77,56) (78,55) (79,54) (79,58) (80,60) (80,60) (82,60) (82,60) (82,62)
`
`(71,48) (73,50) (74,52) (75,50) (77,50) (78,56)
`
`{(85,63) (85,70) (89,75)}
`
`{(79,58) (80,59) (82,61) (82,61) (82,61) (83,62) (85,61) (85,63) (85,66)
`(85,66) (85,66) (85,66) (85,70) (80,63) (87,64) (88,70) (88,75)
`
`{(78,57) (78,59) (78,59) (79,55) (79,56) (79,61) (79,61) (82,60) (82,62)
`(82,62) (82,65) (82,65) (82,65) (83,61) (83,62) (88,72)
`
`{(76,56) (77,54) (78,55)}
`
`the
`threshold we retained the problem. Table 2 lists the parameters of all
`consistent and inconsistent problem instances we reported at site-1, clustered in
`groups of common W* along a DEG ordering. The induced widths along a MIN
`or CARD orderings were highly correlated. Note that most problem instances
`come from a narrow range of parameters. Overall, we experimented with two sets
`of random problems: one containing 66 instances (24 instances were inconsistent),
`each having 10 variables and 5 values, and the other containing 71 instances (39
`instances were inconsistent), each with 15 variables and 5 values. As mentioned,
`these instances represent the moredifficult problems among a muchlargerset of
`probl