Experimental evaluation of modern variable selection strategies in Constraint Satisfaction Problems

Abstract

Constraint programming is a powerful technique for solving combinatorial search problems that draws on a wide range of methods from artificial intelligence and computer science. Constraint solvers search the solution space either systematically, as with backtracking or branch and bound algorithms, or use forms of local search which may be incomplete. Systematic methods typically interleave search and inference. A key factor that can dramatically reduce the search space is the criterion under which we decide which variable will be the next to be instantiated. Numerous heuristics have been proposed for this purpose in the literature. Recent years have seen the emergence of new and powerful methods for choosing variables during CSP search. Some of these methods exploit information about failures gathered throughout search and recorded in the form of constraint weights, while others measure the importance/impact of variable assignments for reducing the search space. In this paper we experimentally evaluate the most recent and powerful variable ordering heuristics, and new variants of them, over a wide range of academic, random and real world problems. Results demonstrate that heuristics based on failures are in general faster. To be precise, heuristic dom/wdeg and its variants are the dominant heuristics in most instances tried.

Introduction

Constraint programming is a powerful technique for solving combinatorial search problems that draws on a wide range of methods from artificial intelligence and computer science. The basic idea in constraint programming is that the user states the constraints and a general purpose constraint solver is used to solve them. Constraints are just relations and a constraint satisfaction problem (CSP) states which relations hold among the given decision variables.

CSPs can be solved either systematically, as with backtracking or branch and bound algorithms, or using forms of local search which may be incomplete. When solving a CSP using backtracking search, a sequence of decisions must be made as to which variable to instantiate next. These decisions are referred to as the variable ordering decisions. It has been shown that for many problems, the choice of variable ordering can have a dramatic effect on the performance of the backtracking algorithm with huge variances even on a single instance.

A variable ordering can be either static, where the ordering is fixed and determined prior to search, or dynamic, where the ordering is determined as the search progresses. Dynamic variable orderings have received much attention in the literature. One common dynamic variable ordering (DVO) strategy, known as “fail-first”, is to select as the next variable the one likely to constrain the remainder of the search space the most. All other factors being equal, the variable with the smallest number of viable values in its (current) domain will have the fewest subtrees rooted at those values, and therefore the smallest search space below it.

Recent years have seen the emergence of numerous modern heuristics for choosing variables during CSP search. Most of them are quite successful and the choice of best general purpose heuristic is not an easy procedure. All these new heuristics, in their original papers, have been tested over a narrow set of problems and they have been compared mainly with older heuristics. Hence, there is no accurate view of the strengths and weaknesses of these heuristics. The aim of this paper is to experimentally compare and evaluate the efficiency of the modern variable ordering heuristics, and new variants of them, over a wide range of academic, random and real world problems.

The rest of the paper is organized as follows. Section 2 gives the necessary background material. In Section 3 we briefly overview the existing variable ordering heuristics, while in Section 4 we give additional details on the heuristics which we have selected for the evaluation. In Section 5 we present experimental results from a wide variety of real, academic and random problems. Finally, a general discussion and conclusions are presented in Section 6. 2

Background

A Constraint Satisfaction Problem (CSP) is a tuple (X, D, C ), where X is a set containing n variables {x1, x2, ..., xn}; D is a set of domains {D(x1), D(x2),..., D(xn)} for those variables, with each D(xi) consisting of the possible values which xi may take; and C is a set of constraints {c1, c2, ..., ck} between variables in subsets of X. Each ci ∈ C expresses a relation defining which variable assignment combinations are allowed for the variables vars(ci) in the scope of the constraint. Two variables are said to be neighbors if they share a constraint. The arity of a constraint is the number of variables in the scope of the constraint. The degree of a variable xi, denoted by Γ(xi), is the number of constraints in which xi participates. A binary constraint between variables xi and xj will be denoted by cij .

An arc (xi,xj ) is arc consistent (AC) iff for every value a ∈ D(xi) there exists at least one value b ∈ D(xj ) such that the pair (a,b) satisfies cij . In this case we say that b is a support of a on arc (xi,xj ). Accordingly, a is a support of b on arc (xj ,xi). A problem is AC iff there are no empty domains and all arcs are AC. The application of AC on a problem results in the removal of all non-supported values from the domains of the variables. The definition of arc consistency for non binary constraints (also called generalized arc consistency, or GAC) is a direct extension of the binary one [ 14, 13 ].

A support check (consistency check) is a test to find out if two values support each other. The revision of an arc (xi,xj ) using AC verifies if all values in D(xi) have supports in D(xj ). A DWO-revision is one that causes a DWO. That is, it results in an empty domain.

A partial assignment is a set of tuple pairs, each tuple consisting of an instantiated variable and the value that is assigned to it in the current search state. A full assignment is one containing all n variables. A solution to a CSP is a full assignment such that no constraint is violated. 3

Overview of existing variable ordering heuristics

The order in which variables are assigned by a backtracking search algorithm has been understood for a long time to be of prime importance. The first category of heuristics used for ordering variables was based on the initial structure of the network. These are called static or fixed variable ordering heuristics (SVOs) as they keep the same ordering of the variables during search. Examples of such heuristics are lexico where variables are ordered lexicographically, min width which chooses an ordering that minimizes the width of the constraint network [ 9 ], min bandwidth which minimizes the bandwidth of the constraint graph [ 20 ], and min degree (deg ), where variables are ordered according to the initial size of their neighborhood [ 8 ].

A second category of heuristics includes dynamic variable ordering heuristics (DVOs) which take into account information about the current state of the problem at each point in search. The first well known dynamic heuristic, introduced by Haralick and Elliott, was dom [ 12 ]. This heuristic chooses the variable with the smallest remaining domain. The dynamic variation of deg, called ddeg selects the variable with largest dynamic degree. That is, the variable that is constrained with the largest number of unassigned variables. By combining dom and deg (or ddeg ), the heuristics called dom/deg and dom/ddeg [ 3, 19 ] were derived. These heuristics select the variable that minimizes the ratio of current domain size to static degree (dynamic degree) and can significantly improve the search performance.

When using variable ordering heuristics, it is a common phenomenon that ties can occur. A tie is a situation where a number of variables are considered equivalent by a heuristic. Especially at the beginning of search, where it is more likely that the domains of the variables are of equal size, ties are frequently noticed. A common tie breaker for the dom heuristic is lexico, (dom+lexico composed heuristic) which selects among the variables with smallest domain size the lexicographically first. Other known composed heuristics are dom+deg [ 10 ], dom+ddeg [ 5, 18 ] and BZ3 [ 18 ].

Bessi`ere et al. [ 2 ], have proposed a general formulation of DVOs which integrates in the selection function a measure of the constrainedness of the given variable. These heuristics (denoted as mDVO ) take into account the variable’s neighborhood and they can be considered as neighborhood generalizations of the dom and dom/ddeg heuristics. For instance, the selection function for variable Xi is described as follows:

Ha!(xi) = !xj∈Γ(xi)(α(xi) ! α(xj )) |Γ(xi)|2 (1) where α(xi) can be any simple syntactical property of the variable such as |D(xi)| or |D(xi)| and ! ∈ {+, ×}. Neighborhood based heuristics have shown to be qu|Γi(txei)p|romising.

Boussemart et al. [ 4 ] proposed conflict-directed variable ordering heuristics. In these heuristics, every time a constraint causes a failure (i.e. a domain wipeout) during search, its weight is incremented by one. Each variable has a weighted degree, which is the sum of the weights over all constraints in which this variable participates. The weighted degree heuristic (wdeg ) selects the variable with the largest weighted degree. The current domain of the variable can also be incorporated to give the domain-over-weighteddegree heuristic (dom/wdeg ) which selects the variable with minimum ratio between current domain size and weighted degree. Both of these heuristics (especially dom/wdeg ) have been shown to be extremely effective on a wide range of problems.

Grimes and Wallace [ 11 ] proposed alternative conflict-driven heuristics that consider value deletions as the basic propagation events associated with constraint weights. That is, the weight of a constraint is incremented each time the constraint causes one or more value deletions. They also used a sampling technique called random probing with which they can uncover cases of global contention, i.e. contention that holds across the entire search space.

Inspired from integer programming, Refalo introduced an impact measure with the aim of detecting choices which result in the strongest search space reduction [ 16 ]. An impact is an estimation of the importance of a value assignment for reducing the search space. He proposes to characterize the impact of a decision by computing the Cartesian product of the domains before and after the considered decision. The impacts of assignments for every value can be approximated by the use of averaged values at the current level of observation. If K is the index set of impacts observed so far for assignment xi = α, I is the averaged impact:

" Ik(xi = α) I(xi = α) = k∈K I(xi) =

" α∈D(xi) 1 − I(xi = α) (2) (3) |K| The impact of a variable xi can be computed by the following equation: An interesting extension of the above heuristic is the use of “node impacts” to break ties in a subset of variables that have equivalent impacts. Node impacts are the accurate impact values which can be computed for any variable by trying all possible assignments.

Correia and Barahona [ 7 ] propose variable orderings, by integrating Singleton Consistency propagation procedures with look-ahead heuristics. This heuristic is similar to “node impacts”, but instead of computing the accurate impacts, it computes the reduction in the search space after the application of Restricted Singleton Consistency (RSC) [ 15 ], for every value of the current variable. Although this heuristic was firstly introduced to break ties in variables with current domain size equal to 2, it can also be used as a tie breaker for any other variable ordering heuristic.

Cambazard and Jussien [ 6 ] go a step further by analyzing where the reduction of the search space occurs and how past choices are involved in this reduction. This is implemented through the use of explanations. An explanation consists of a set of constraints C" (a subset of the set C of the original constraints of the problem) and a set of decisions dc1, ..., dcn taken during search. An explanation of the removal of value a from variable v can be written as:

C" ∧ dc1 ∧ dc2 ∧ ... ∧ dcn ⇒ v &= a

Finally, Balafoutis and Stergiou [ 1 ], propose new variants of conflictdriven heuristics. These variants differ from wdeg in the way they assign weights. They propose heuristics that record the constraint that is responsible for any value deletion during search, heuristics that give greater importance to recent conflicts, and finally heuristics that try to identify contentious constraints by detecting all possible conflicts after a failure. The last heuristic, called “fully assigned”, increases the weights of constraints that are responsible for a DWO by one (as wdeg heuristic does) and also, only for revision lists that lead to a DWO, increases by one the weights of constraints that participate in fruitful revisions (revisions that delete at least one value). Hence, this heuristic records all variables that delete at least one value during constraint propagation and if a DWO is detected, it increases the weight of all these variables by one.

Details on the evaluated heuristics

For the evaluation we have selected heuristics from 5 recent papers mentioned above. These are: i) dom/wdeg from Boussemart et al. [ 4 ], ii) the random probing technique and “alldel by #del” heuristic where constraint weights are increased by the size of the domain reduction (Grimes and Wallace [ 11 ]), iii) Impacts and Node Impacts from Refalo [ 16 ], iv) the “RSC” heuristic from Correia and Barahona [ 7 ] and finally v) the “fully assigned” heuristic from Balafoutis and Stergiou [ 1 ].

We have also included in our experiments some combinations of the above heuristics. For example, dom/wdeg can be combined with RSC (in this case RSC is used only to break ties). Random probing can be applied to any conflict-driven DVO, hence it can be used with the dom/wdeg and “fully assigned” heuristics. Moreover, the impact heuristic can be combined with RSC for breaking ties.

The full list of the heuristics that we have tried in our experiments includes 15 variations. These are the following: 1) dom/wdeg, 2) dom/wdeg + RSC (the second heuristic is used only for breaking ties), 3) dom/wdeg with random probing, 4) dom/wdeg with random probing + RSC, 5) Impacts, 6) Node Impacts, 7) Impacts + RSC, 8) alldel by #del, 9) alldel by #del + RSC, 10) alldel by #del with random probing, 11) alldel by #del with random probing + RSC, 12) fully assigned, 13) fully assigned + RSC, 14) fully assigned with random probing, and 15) fully assigned with random probing + RSC. In all these variations the RSC heuristic is used only for breaking ties. 5

Experiments and results

We now report results from the experimental evaluation of the selected DVOs described above on several classes of problems. In Section 5.1 we present results from the radio link frequency assignment problem (RLFAP). In Section 5.2 we present results from structured problems. These instances are taken from some academic (langford), real world (driver) and patterned (graph coloring) problems. In Section 5.3 we consider instances from quasirandom and random problems. The last experiments presented in Section 5.4 include Boolean instances. Finally in Section 5.5 we make a general discussion where we summarize our results.

In the experiments we used MGAC (maintaining generalized arc consistency) [ 17, 3 ] as our search algorithm. In MGAC a problem is made generalized arc consistent after every assignment, i.e. all values which are generalized arc inconsistent given that assignment, are removed from the current domains of their variables. If during this process a domain wipeout (DWO) occurs, then the last value selected is removed from the current domain of its variable and a new value is assigned to the variable. If no new value exists then the algorithm backtracks.

All benchmarks are taken from C. Lecoutre’s web page1, where the reader can find additional details on how the benchmarks are constructed. In our experiments we included both satisfiable and unsatisfiable instances. Each selected instance involves constraints defined either in intension or in extension (we have not included instances expressed with global constraints).

We have used two measures of performance for the DVOs tested: cpu time in seconds (t) and number of visited nodes (n). The solver we used applies d-way branching, and lexicographic value ordering. It also employs restarts. Concerning the restart policy, the initial number of allowed backtracks for the first run has been set to 10 and at each new run the number of allowed backtracks increases by a factor of 1.5.

In our experiments the random probing technique is run to a fixed cutoff C = 40, and for a fixed number of restarts R = 50 (these are the optimal values from [ 11 ]). Cpu time and nodes for random probing are averaged values for 10 runs. For this heuristic, we have measured the total cpu time and the total nodes visited (from both random probing initialization and final search). However, in the next tables (except Table 1) we have also put in parenthesis results from the final search only (random probing initialization is excluded).

Concerning impacts, we have approximated their values at the initialization phase by dividing the domains of the variables into (at maximum) four sub-domains. In all the experiments, a time out limit has been set to 1 hour. 5.1

RLFAP instances

The Radio Link Frequency Assignment Problem (RLFAP) is the task of assigning frequencies to a number of radio links so that a large number of constraints are simultaneously satisfied and as few distinct frequencies as possible are used. A number of modified RLFAP instances have been produced from the original set of problems by removing some frequencies (denoted by f followed by a value). For example, scen11-f8 corresponds to the instance scen11 for which the 8 highest frequencies have been removed.

Results from Table 1 show that conflict-driven heuristics (dom/wdeg, alldel and fully assigned) have the best performance. The Impact heuristic seems to make a better exploration of the search tree on some easy instances (like s2-f25, s11, s11-f12, s11-f11), but it is slower compared to conflict-driven heuristics. This is mainly because the process of impact initialization is time consuming. However, on hard instances, the Impact heuristic has worse performance and in some cases it cannot solve the problem within the time 1http://www.cril.univ-artois.fr/∼lecoutre/research/benchmarks/ limit. In general we observed that impact based heuristics cannot handle efficiently problems which include variables with relatively large domains. RLFA problems, for example, have 680 variables with maximum 44 values in their domains.

Node Impact and its variation, “Impact RSC”, are strongly related, and this similarity is depicted in the results. As mentioned in Section 3, Node Impact computes the accurate impacts and “RSC” heuristic computes the reduction in the search space, after the application of Restricted Singleton Consistency. Since node impact computation also uses Restricted Singleton Consistency (it subsumes it), these heuristics differ only in the measurement function that assigns impacts to variables. Hence, when they are used to break ties on the Impact heuristic, they usually make similar decisions.

When “RSC” is used as a tie breaker for conflict-driven heuristics, results show that it does not offer significant changes in the performance. So we have excluded it from the experiments that follow in the next sections, except for the dom/wdeg + RSC combination.

Concerning “random probing”, although experiments in [ 11 ] show that it has often better performance when compared to simple dom/wdeg, our results show that this is not the case when dom/wdeg is combined with a geometric restart strategy. Even on hard instances, where the computation cost of random probes is smaller (compared to the total search cost) results show that dom/wdeg and its variations are dominant. Moreover, the combination of “random probing” with any other conflict-driven variation heuristic (“alldel” or “fully assigned”) does not offer significant changes. Thus, for the next experiments we have kept only the “random probing” and dom/wdeg combination.

Finally, among the three conflict-driven variations, in this set of benchmarks, dom/wdeg seems to have a slightly better performance. 5.2

Structured instances

This set of experiments contains instances from academic problems (langford), some real world instances from the “driver” problem and 6 graph coloring instances.

Since some of the variations presented in the previous paragraph (Table 1) were shown to be less interesting, we have omitted their results from the next tables.

Results in Table 2 show that the behavior of the selected heuristics is close to the behavior that we observed in RLFA problems. Conflict-driven variations are again dominant here. The dom/wdeg heuristic has in most cases the best performance, followed by “alldel” and “fully assigned”.

Although random probing has in most experiments worse cpu times compared to dom/wdeg, we have to notice that in the langford2-10 instance it is faster. Impact based heuristics have by far the worst performance. gd llyu SC ,17 097 ,47 58 ,02 908 ,82 480 ,15 132 ,039 4626 ,325 2866 ,2275 692 ,46 360 ,46 360 ,67 604 26 482 ,68 137 ,965 6550 ,091 2947 n f R 1 1 1 4 1 1 3 3 1 1 1 3 2 1 1 5 5 a T f .

r s e

1 5 8 6 6 9 6 4 7 4 7 9 0 8 4 9 9 4 3 e lly bo 2 ,5 4 ,5 0 ,6 8 ,7 5 , 9 , 6 , 2 h u rp ,372 772 ,441 860 ,587 048 ,915 529 76 357 ,525 614 ,584 615 ,04 94 96 64 66 24 67 43 68 94 90 28 71 64 14 13 1 1 2 2 2 2 2 1 3 2 2 2 2 1 2 2 4 4 7 le be 1 2 4 8 6 9 1 6 5 3 0 9 6 1 8 8 7 is ld ro SC ,61 83 ,55 57 ,95 78 ,97 94 ,77 68 ,77 91 ,68 60 , 8 22 e l p R 2 5 3 6 4 8 6 2 6 1 7 2 4 1 09 815 ,589 185 ,612 228 60 155 ,801 205 69 509 275 807 ,0 8 a .r 1 1 1 2 2 4 2 1 2 2 2 2 2 2 4 4 6 m i t l

e C 5 5 u

0 3 9 2 5 9 9 0 1 4 0 ,7 62 ,1 57 ld S ,1 81 ,69 386 61 19 30 51 ,13 425 ,776 844 ,739 950 ,176 1263 7 07 ,1 89 ,44 496 23 58 ,0 90 39 42 88 61 cp la R 1 2 2 4 3 1 1 1 1 1 1 4 3 1 2 3 5 t s e le be

2 0 6 0 4 3 1 2 9 0 6 2 5 7 0 B ld ro ,361 705 ,488 799 ,698 065 ,835 599 ,871 400 ,855 965 274 3303 134 358 ,801 398 ,789 427 ,869 349 ,957 457 102 853 225 524 682 638 l p .s a .r 1 1 2 2 2 3 1 3 2 2 2 2 2 4 8 lebm lled ,6 50 ,9 5 ,8 51 ,7 82 ,7 68 ,60 365 ,3 71 ,8 46 ,9 21 ,6 14 ,8 54 ,67 799 ,26 177 ,77 379 ,91 989 ro la 9 22 1 46 61 22 22 66 2 5 3 18 2 11 5 9 2 6 2 4 2 4 1 1 2 2 31 17 42 53 ,75 8115 2 10 ,4 69 ,9 2 6 ,9 03 ,8 68 ,8 36 ,9 48 ,8 48 ,3 74 ,72 767 ,45 879 ,893 6139 ,913 6331 6 7 9 21 631 4 39 22 141 16 73 4 8 2 4 2 4 4 6 1 1 3 2 1 2 2 3 t n t n t n t n t n t n t n t n t n t n t n t n t n t n t n : r le1b fodn tscean f-s225 (t)saun f-s130 t()sa f-s131 (t)saun f-g810 (t)sa f-18g1 (t)sanu f-24g17 )t(sa f-2841 t)sanu s11 t)(sa f-s1121 t)(sanu f-s1111 )t(saun f-s0111 )t(saun f-s191 t)(saun f-s181 t)(saun f-s171 t)(saun f-s161 t)(saun a ta In g ( T s 5.3

Random instances

In this set of experiments we have selected some quasi-random instances which contain some structure (“ehi” and “geo” problems) and also some purely random instances, generated following Model RB and Model D.

Model RB instances (frb30-15-1 and frb30-15-2), are random instances forced to be satisfiable. Model D instances are described by four numbers <n,d,e,t >. The first number n corresponds to the number of variables. The second number d is the domain size and e is the number of constraints. t is the tightness, which denotes the probability that a pair of values is allowed by a relation.

Results are presented in Table 3. All the conflict-driven heuristics (dom /wdeg, “alldel” and “fully assigned”) have very similar node visits and much better cpu times compared to impact based heuristics. In pure random problems the “alldel” heuristic has the best cpu times, while in quasi-random instances the three conflict-driven heuristics share a win. 5.4

Boolean instances

This set of experiments contains instances involving only Boolean variables. We have selected a representative subset from Dimacs problems. All the selected instances have constraint arity equal to 3, except for the “jnhSat” instances which have maximum arity of 14.

Results from these experiments can be found in Table 4. The behavior of the evaluated heuristics in this data set is slightly different from the behavior that we observed in previous problems. Although conflict-driven heuristics again display here the best overall performance, impact based heuristics are in some cases faster.

One of the main bottlenecks that impact based heuristics have, is the time consuming initialization process. On binary instances, where the variables have binary domains, the cost for the initialization of impacts is small. And this can significantly increase the performance of these heuristics.

We observed also that in ‘jnhSat” instances (which include constraints with maximum arity of 14)the Impact heuristic is in all cases faster than dom/wdeg. This result, have lead us to an empirical presumption that on binary problems with high constraint arity, the Impact heuristic is quite strong.

Among the conflict-driven heuristics, the “alldel” heuristic is always better than its competitors. We recall here that in this heuristic, constraint weights are increased by the size of the domain reduction. Hence, on binary instances constraint weights can be increased at minimum by one and at maximum by two (in each DWO). This way of incrementing weights seems to work better on binary problems.

However, all these empirical remarks are quite preliminary and further work must be done is this and other classes of non-binary problems in order to achieve a better understanding of why these differentiations in performance exist. 5.5

A general summary of the results

In order to get a summarized view of the evaluated heuristics, we present two figures. In these figures we have computed averaged values for runtime and node visits for the three major conflict-driven variants (dom/wdeg, “alldell” and “fully assigned”) and we have compared them graphically to the Impact heuristic (which has the best performance among the impact based heuristics).

Results are collected in Figure 1. The left plot in this figure corresponds to run times and the right plot to visited nodes. Each point in these plots, shows the runtime (or nodes visited) for one instance from all the presented benchmarks. The y-axis represent the solving time (or nodes visited) for the Impact heuristic and the x-axis the averaged values for the conflict-driven heuristics. Therefore, a point above line y = x represents an instance which is solved faster (or with less node visits) using the conflict-driven heuristics. jnh01 t 10,5 (sat) n 966 jnh17 t 3,2 (sat) n 477 jnh201 t 3,1 (sat) n 336 jnh301 t 38,4 (sat) n 2703 aim-50-1- t 0,18 6-unsat-2 n 1766 aim-100-1- t 0,4 6-unsat-1 n 3965 aim-200-1- t 0,8

6-sat-1 n 5099 aim-200-1- t 2,1 6-unsat-1 n 14453 pret-60- t 1517 25 (unsat) n 48,1M dubois-20 t 1424 (unsat) n 48,4M Both axes are logarithmic.

As we can clearly see from Figure 1 (left plot), conflict-driven heuristics are almost always faster. Concerning node visits, the right plot does not reflect an identical performance. Although it seems that in most cases conflict-driven heuristics are making a better exploration in the search tree, these exists a considerable set of instances where the Impact heuristic visit less nodes. 6

Conclusions

In this paper we experimentally evaluate the most recent and powerful variable ordering heuristics, and new variants of them, over a wide range of academic, random and real world problems. These heuristics can be divided in two main categories: heuristics that exploit information about failures gathered throughout search and recorded in the form of constraint weights and heuristics that measure the importance/impact of variable assignments for reducing the search space. Results demonstrate that, in general, heuristics based on failures have much better cpu performance. Although impact based heuristics are in general slow, there are some cases where they perform a smarter exploration of the search tree resulting in fewer node visits.

This paper is only a preliminary step towards evaluating and (crucially) understanding the behavior of modern variable ordering heuristics. As results presented here demonstrated, both major strategies for variable selection, conflicts and impacts, have strengths and weaknesses. We believe that the development of hybrid techniques that exploit the strengths of both strategies should be a important topic for future research.

References

[1] T. Balafoutis and K. Stergiou . On conflict-driven variable ordering heuristucs . In Proceedings of the ERCIM workshop - CSCLP , 2008 .

[2] C. Bessi `ere, A . Chmeiss, and L. Sais . Neighborhood-based variable ordering heuristics for the contraint satisfaction problem . In Proceedings of CP'01 , pages 61 - 75 , 2001 .

[3] C. Bessi `ere and J.C. R ´egin. MAC and combined heuristics: two reasons to forsake FC (and CBJ?) . In In Proceedings of CP-1996 , pages 61 - 75 , Cambridge MA, 1996 .

[4] F. Boussemart , F. Hemery , C. Lecoutre , and L. Sais . Boosting systematic search by weighting constraints . In In Proceedings of 16th European Conference on Artificial Intelligence (ECAI '04) , Valencia, Spain, 2004 .

[5] D. Brelaz . New methods to color the vertices of a graph . Communications of the ACM , 22 : 251 - 256 , 1979 .

[6] H. Cambazard and N. Jussien . Identifying and Exploiting Problem Structures Using Explanation-based Constraint Programming . Constraints , 11 : 295 - 313 , 2006 .

[7] M. Correia and P. Barahona . On the integration of singleton consistency and look-ahead heuristics . In Proceedings of the ERCIM workshop - CSCLP , 2007 .

[8] R. Dechter and I. Meiri. Experimental evaluation of preprocessing techniques in constraint satisfaction problems . In In Proceedings of IJCAI'89 , pages 271 - 277 , 1989 .

[9] E.C. Freuder . A sufficient condition for backtrack-free search . Journal of the ACM , 29 ( 1 ): 24 - 32 , 1982 .

[10] D. Frost and R. Dechter . Look-ahead value ordering for constraint satisfaction problems . In In Proceedings of IJCAI'95 , pages 572 - 578 , 1995 .

[11] D. Grimes and R.J. Wallace . Sampling strategies and variable selection in weighted degree heuristics . In In Proceedings of CP 2007 , pages 831 - 838 , 2007 .

[12] R.M. Haralick and Elliott. Increasing tree search efficiency for constraint satisfaction problems . Artificial Intelligence , 14 : 263 - 314 , 1980 .

[13] A. Mackworth . On reading sketch maps . In In Proceedings of IJCAI'77 , pages 598 - 606 , Cambridge MA, 1977 .

[14] R. Mohr and T.C. Henderson . Arc and path consistency revisited . Artificial Intelligence , 28 : 225 - 233 , 1986 .

[15] P. Prosser , K. Stergiou , and T. Walsh . Singleton consistencies . In Proceedings of CP'00 , pages 353 - 368 , 2000 .

[16] P. Refalo . Impact-based search strategies for constraint programming . In In Proceedings of CP 2004 , pages 556 - 571 , 2004 .

[17] D. Sabin and E.C. Freuder . Contradicting conventional wisdom in constraint satisfaction . In In Proceedings of CP '94 , pages 10 - 20 , 1994 .

[18] B.M. Smith. The brelaz heuristic and optimal static orderings . In In Proceedings of CP'99 , pages 405 - 418 , 1999 .

[19] B.M. Smith and S.A. Grant . Trying harder to fail first . In In Proceedings of ECAI'98 , pages 249 - 253 , 1998 .

[20] R. Zabih . Some applications of graph bandwith to constraint satisfaction problems . In In Proceedings of AAAI'90 , pages 46 - 51 , 1990 .