`
`, A};
`ELEVIER
`
`Artificial Intelligence 68 (1994) 211—241
`
`ICAL REPORT
`TECHN
`TECHNICAL REPORT
`R-121-AI
`R-121-AI
`
`
`
`Artificial
`
`Intelligence
`
`
`Experimental evaluation of preprocessing algorithms for
`constraint satisfaction problems
`
`Rina Dechtera’*, Itay Meirib
`3Information and Computer Science Department, University of California, Irvine, CA 29717—3425,
`USA
`
`bCognitive 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 rearrangement is 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 B.V. All rights reserved
`SSDI 0004-3702(93)E0057-S
`
`CONFIGIT 1047
`
`CONFIGIT 1047
`
`1
`
`
`
`212
`
`R. Dechter. I. Meiri
`
`/ Artificial Intelligence 68 (1994) 211—241
`
`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.
`We organized 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 guaranteed to yield a solution in time bounded by O(exp(W*)),
`where W* is a parameter reflecting the sparseness of the network.
`Our results show, contrary to predictions based on worst—case analysis, that the
`average complexity of backtracking on our randomly generated problems is 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 of its
`theoretical superiority to backtracking. On the other hand, the least aggressive
`scheme, DAC, came out as a winner
`in computationally intensive cases.
`Apparently, DAC performs just the desired amount of preprocessing. Additional-
`ly, while ADAPT showed that its 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 DPC as 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 our static
`ordering with one dynamic ordering, dynamic search rearrangement (DSR) [21].
`We tested two implementation styles of DSR, presenting a tradeoff between space
`and time overhead.
`
`results show that minimum width and maximum cardinality clearly
`Our
`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 remarks in Section 6.
`
`2. Constraint processing techniques
`
`. ,Xn},
`.
`A constraint network (CN) consists of a set of variables X = {X1, .
`each associated with a domain of discrete values D1, .
`.
`.
`, D", and a set of
`constraints {C1, .
`.
`.
`, 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, are legal.1
`
`1 This does not mean that the actual representation of any constraint is necessarily in the form of its
`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~24l
`
`. *Xim)
`.
`Formally, constraint C,- has two parts: a subset of variables S, = {XW .
`on which it is defined, called a constraint-subset, and a relation rel, defined over
`5,: rel, g Dir X -
`-
`- >< Dim" The scheme of a CN is the set of its constraint subsets,
`namely, scheme(CN) = {S,, 52, .
`.
`. ,St}, S, QX. An assignment of a unique
`domain value to each member of 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 ={(X1=xl, .
`
`.
`
`. ,Xn =xn)|VSi Escheme, HSip greli},
`
`(1)
`
`where HXp is the projection of relation 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 be associated 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 whether a solution exists, finding
`one solution or the set of all 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).
`
`0,; = {hoses,laser,sheet,snnil,steer}
`DA :00 = {hike,aron,keet,earn,same}
`Dc = {run,sun,1et ,yes,eat ,ten}
`DB = {no,be,us,it}
`
`(snail , aron) , (steer, earn)}
`
`CAB = {(hoses.sme) , (laser,same) . (sheet,earn) ,
`
`(C)
`(b)
`is the constraint between
`Fig. 1. (a) A crossword puzzle (D denotes domains of variables, CM,
`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 be classified into three
`categories: (1) search algorithms, for systematic exploration of the space of all
`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,
`where a 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
`ADAPT are all restricted (because they take into account the direction in which
`backtracking instantiates the variables) versions of these consistency enforcing
`algorithms.
`The preprocessing algorithms also 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 schemes or look-back schemes. Look-ahead schemes
`
`to assign a value to the next
`are invoked whenever the algorithm is about
`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 scheme is
`dynamic search rearrangement, which decides what variable to instantiate next
`
`5
`
`
`
`216
`
`R. Dechter, I. Meiri
`
`/ Artificial Intelligence 68 (1994) 2117241
`
`[10, 21, 26]. Look-back schemes are invoked when the algorithm encounters a
`deadend and prepares to backtrack. An example of such a scheme is backjumping
`[12]. By analyzing the reasons for the deadend it 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 deadend so 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
`
`We first 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(x1, .
`.
`.
`, xi, X.- H), which selects
`all values in the domain of variable Xi+1 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
`deadend occurs at variable X, it backs up to the most recent variable Y connected
`to X in the constraint graph. If variable Y has no more values, 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(x1, .
`.
`.
`, xi,xi+1, P)
`and jump-back(x1, .
`.
`. ,xi, Xi +1, P). Procedure jump-back is shown in Fig. 3. Its
`parameters are the partial instantiation x1, .
`.
`. ,xi, the deadend variable Xi“,
`and P.
`
`6
`
`
`
`R. Dechter, I. Meiri
`
`/ Artificial Intelligence 68 (1994) 211—241
`
`217
`
`
`
`.
`
`. ,xi)
`
`forward(x1, .
`Begin
`1.
`if i= n, exit with the current assignment
`2. CH1(—compute-candidatesoc], .
`.
`. ,xi, Xi“)
`3.
`if Ci+1 is not empty then
`4
`xi+1<—first element in CH1, and
`5.
`remove xi+1 from CH1, and
`.
`forward(x1,...,xi,xi+1)
`. Else
`
`go-back(x1, .
`
`.
`
`. ,xl.)
`
`6 7 8
`
`.
`End
`
`.
`
`. ,x,)
`
`go-back(x1, .
`Begin
`1.
`if 1': 0, exit (no solution exists)
`2.
`if Cl. is not empty then
`3.
`xi<—first in Ci, and
`4.
`remove xi from Ci, and
`5.
`forward(x1, .
`.
`. ,xi)
`6. Else
`
`7.
`End
`
`
`.
`
`. ,xi_1)
`
`go-back(x1, .
`
`Fig. 2. Algorithm backtracking.
`
`jump-back(x1, .
`Begin
`
`.
`
`. ,xi,X,+1, P)
`
`PWSQMPWNE
`
`if i= 0, exit (no solution exists)
`. PARENTSe—Parents2(Xi+1)
`P (—P U PARENTS
`
`Let j be the largest indexed variable in P,
`P <——P - X].
`if C]. #95 then
`x]. = first in C], and
`remove x]. from Ci, and
`forward(x1, .
`.
`. ,xj, P)
`10. Else
`
`. ,xi_1,Xj, P)
`.
`jump-back(x1, .
`11.
`End
`
`
`Fig. 3. Procedure jump-back.
`
`2 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~24l
`
`Consider, for instance, the ordered constraint graph in Fig. 1(a). If the search is
`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 DFS tree) 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. 1(c). The
`directed arcs are part of the DFS tree. The rest of the arcs are undirected [8]. The
`DFS ordering (which amounts to an in—order traversal 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. As the 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
`uncover this 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.
`We start 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 nodes in 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
`
`C
`
`D
`
`E
`
`(a)
`
`(b)
`
`Fig. 4. Ordered constraint graphs.
`
`width of all 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, shown in Fig.
`5, processes the nodes in a reverse order, that is, each node is processed before
`any of its parents.
`The procedure record-c0nstraint(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 have their 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
`{(eam, run), (earn, sun), (earn, ten)}. ADAPT may tighten 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
`
`.
`
`. ,XN)
`
`ADAPT(X1, .
`Begin
`1. for i=n to 1 by —1 do
`2.
`compute parents(X,.)
`3.
`perform record-constraint(Xi, parents(X,.))
`4.
`in the
`constraint graph,
`connect
`all unconnected elements
`parents(X,.)
`
`End
`
`Fig. 5. Algorithm ADAPT.
`
`in
`
`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 common successor .
`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. The resulting 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
`ADAPT only in the amount and size of constraint recording performed in Step 3.
`Namely, instead of recording one constraint among all parents, they record a few
`smaller constraints on subsets of the parents. Let level 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 induced by all 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.
`
`.
`
`. ,X")
`
`adaptive(level, X1, .
`Begin
`1.
`2.
`3.
`4.
`End
`
`fori=ntolby—1do
`compute parents(X,.)
`perform new-record(level, Xi, parents(Xi))
`for level 2 2, connect in the graph all elements in parents(X,)
`
`new-record(level, var, set)
`Begin
`1.
`if level $ lsetl then
`2.
`for every subset S in set, subject to IS I = level do
`3.
`record-c0nstraint(var, S)
`4.
`end
`
`5. else do record-c0nstraint(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<(W*(d)> . (kmin{level,W“(d)))> ’
`
`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.
`We consider 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 number of its 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 that is
`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
`
`the choice of such a variable
`with the current partial solution. Heuristically,
`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-l 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 (3]) 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. At site-2 we studied only the effect of ordering
`strategies, with and without preprocessing by arc consistency.
`In this case we
`executed backtracking and backjamping 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-BI (i.e., DPC followed by backjumping)
`was tested only at site-1, while B] was tested at both site-1 and site-2. Note that
`an instance-by—instance comparison is feasible only within sites.
`The test problems at each site were generated using the same random model,
`but with different parameters. The generator used four parameters: n,
`the
`number of variables; k, the number of values; and p1 and p2. The parameter p1
`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 p2 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 p1 and then
`created a relation for each arc in the graph using probability p2 (p2 is the
`probability of a no—good). This
`random model has been used by others
`[3,12,14].3 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 p1 and p2 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
`B]
`DAC
`DPC
`ADAPT
`
`
`
`
` B] B] B] B TK B TK B TK
`
`
`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
`.
`.
`.
`.
`.
`Additlonal, more recently used random models are discussed in the conclusron.
`
`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 ha