Con ict History Based Branching Heuristic for CSP Solving?

Abstract

An important feature in designing algorithms to solve Constraint Satisfaction Problems (CSP) is the de nition of a branching heuristic to explore e ciently the search space and exploit the problem structure. We propose Con ict-History Search (CHS), a new dynamic and adaptive branching heuristic for CSP solving. It is based on the search history by considering the temporality of search failures. To achieve that, we use the exponential recency weighted average to estimate the evolution of the hardness of constraints throughout the search. The experimental evaluation on XCSP3 instances shows that integrating CHS to solvers based on MAC obtains competitive results and can improve those obtained through other heuristics of the state of the art.

Keywords

• CSP
• Con ict Based Branching Heuristic
• Search History
• Exponential Recency Weighted Average

Introduction

The Constraint Satisfaction Problem (CSP) is a powerful framework to model and e ciently solve problems that occur in various elds, both academic and industrial [ 21 ]. A CSP instance is de ned on a set of variables which must be assigned in their respective nite domains by satisfying a set of constraints which express restrictions between di erent assignments. A solution is an assignment of each variable which satis es all constraints.

CSP solving has made signi cant progress in recent years thanks to research on several aspects which receive considerable e orts such as global constraints, ltering techniques, learning and restarts. An important component in CSP solvers is the variable branching rule. Indeed, the corresponding heuristics dene, statically or dynamically, the order in which the variables will be assigned and thus the way that the search space will be explored.

Many heuristics have been proposed (e.g. [1{4, 6, 7, 9, 18, 20]) and aim to satisfy the famous rst-fail principle [ 8 ] which advises "to succeed, try rst where you are likely to fail". Nowadays, the most e cient heuristics are adaptive and dynamic [ 3, 6, 9, 18, 20 ]. Indeed, the order of branchings is de ned according to ? This work has been funded by the french Agence Nationale de la Recherche, reference

ANR-16-C40-0028. the collected information since the beginning of the search. For instance, some heuristics consider the e ect of ltering when decisions and propagations are applied [ 18, 20 ]. De ned since 2004, the dom=wdeg heuristic remains one of the simplest, the most popular and e cient one. It is based on the hardness of constraints to re ect how often a constraint fails. It uses a weighting process to focus on the variables appearing in constraints with high weights which are assumed to be hard to satisfy [ 3 ].

In this paper, we propose Con ict-History Search (CHS), a new dynamic and adaptive branching heuristic for CSP solving. It is based on the history of search failures which happen as soon as a domain of a variable is emptied after constraint propagations. The goal is to reward the scores of constraints that have recently been involved in con icts and therefore to favor the variables appearing in these constraints. The scores of constraints are estimated on the basis of the exponential recency weighted average technique which comes from reinforcement learning [ 24 ]. It was also recently used in de ning powerful branching heuristics for solving the satis ability problem (SAT) [ 15, 16 ]. We have integrated CHS in solvers based on MAC [ 22 ] and BTD [ 12 ]. The empirical evaluation on XCSP3 instances shows that CHS is competitive and brings improvements to the heuristics of the state of the art.

The paper is organized as follows. Section 2 includes some necessary de nitions and notations. Section 3 describes related work on branching heuristics for CSP and SAT. Section 4 presents and details our contribution which is evaluated experimentally in Section 5. Finally, we conclude and give future work. 2

Preliminaries

We give some de nitions including CSP and Exponential Recency Weighted Average (ERWA). 2.1

Constraint Satisfaction Problem

An instance of a Constraint Satisfaction Problem (CSP) is given by a triple (X; D; C), such that: { X = fx1; ; xng is a set of n variables, { D = fD1; :::; Dng is a set of nite domains, and { C = fc1; ; ceg is a set of e constraints.

Each constraint ci is de ned by S(ci) and R(ci), where S(ci) = fxi1 ; ; xik g X de nes the scope of ci and R(ci) Di1 Dik is its compatibility relation. The constraint satisfaction problem asks for an assignment of a value from Di to each variable xi of X that satis es each constraint in C. Checking whether a CSP instance has a solution (i.e. a consistent assignment of X) is NP-complete.

Exponential Recency Weighted Average

Given a time series of m numbers y = (y1; y2; ; ym), the simple average of y is Pm 1 yi where each yi has the same weight m1 . However, recent data may i=1 m be more pertinent than the older ones to characterize the current situation. The Exponential Recency Weighted Average (ERWA) [ 24 ] takes into account such considerations by giving to the recent data higher weights than the older ones. In fact, the exponential moving average ym is computed by: ym = Pim=1 :(1 )m i:yi, where 0 < < 1 is a step-size parameter which controls the relative weights between recent and past data. The moving average can also be calculated incrementally by the formula: ym+1 = (1 ):ym + :ym+1.

ERWA was used to solve the bandit problem to estimate the expected reward of di erent actions in non-stationary environments [ 24 ]. In bandit problems, there is a set of actions and the agent must select the action to play in order to maximize its long term expected reward. 3

Related Work

We present the most e cient branching heuristics for CSP and SAT. The recalled heuristics share the same behavior. Indeed, the variables and/or constraints are weighted dynamically throughout the search by considering the collected information since the beginning of the search. Also, some heuristics smooth (or decay) these weights as it will be explained further. 3.1

Impact-Based Search (IBS)

This heuristic selects the variable which leads to the largest search space reduction [ 20 ]. This impact on the search space size is approximated as the reduction of the product of the variable domain sizes. Formally, the impact of assigning the variable xi to the value vi 2 Di is de ned by I(xi = vi) = 1 PPbaefftoerre . Pafter and Pbefore are respectively the products of the domain cardinalities after and before branching on xi = vi and applying constraint propagations. 3.2

Con ict-Driven Heuristic

A popular branching heuristic for CSP solving is dom=wdeg [ 3 ]. It guides the search towards the variables appearing in the constraints which seem to be hard to satisfy. For each constraint cj , the dom=wdeg heuristic maintains a weight w(cj ) (initially set to 1) counting the number of times that cj has led to a failure (i.e. the domain of a variable xi in S(cj ) is emptied during propagation thanks to cj ). The weighted degree of a variable xi is de ned as: wdeg(xi) =

X with U vars(cj ) the set of unassigned variables in S(cj ). The dom=wdeg heuristic selects the variable xi to branch on with the smallest ratio jDij=wdeg(xi), such that Di is the current domain of xi (potentially, the size of Di may be reduced by the propagation process in the current step of the search). The constraint weights are not smoothed in dom=wdeg. Variants of dom=wdeg were introduced (for example, see [ 9 ]). 3.3

Activity-Based Heuristic (ABS)

This heuristic is motivated by the prominent role of ltering techniques in CSP solving [ 18 ]. It exploits this ltering information and maintains measures of how often the variable domains are reduced during the search. Indeed, at each node of the search tree, constraint propagation may lter the domains of some variables after the decision has been made. Let Xf be the set of such variables. Accordingly, the activities A(xi) (initially set to 0) of the variables xi 2 X are updated as follows: A(xi) = A(xi) + 1 if xi 2 Xf and A(xi) = A(xi) if xi 62 Xf . is a decay parameter, such that 0 1. The ABS heuristic selects the variable xi with the highest ratio A(xi)=jDij. 3.4

Branching Heuristics for SAT

In the context of the satis ability problem (SAT), modern solvers based on Con ict-Driven Clause Learning (CDCL) [ 5, 17, 19 ] employ variable branching heuristics correlated to the ability of the variable to participate in producing learnt clauses when con icts arise (a con ict is a clause falsi cation). The Variable State Independent Decaying Sum (VSIDS) heuristic [ 19 ] maintains an activity value for each Boolean variable. The activities are modi ed by two operations: the bump (increase the activity of variables appearing in the process of generating a new learnt clause when a con ict is analyzed) and the multiplicative decay of the activities (often applied at each con ict). VSIDS selects the variable with the highest activity to branch on.

Recently, a con ict history based branching heuristic (CHB) [ 15 ], based on the exponential recency weighted average, was introduced. It rewards the activities to favor the variables that were recently assigned by decision or propagation. The rewards are higher if a con ict is discovered1. The Learning Rate Branching (LRB) heuristic [ 16 ] extends CHB by exploiting locality and introducing the learning rate of the variables. 4

Con ict-History Search for CSP

Inspired by the CHB heuristic for SAT, we de ne a new branching heuristic for CSP solving which we call Con ict-History Search (CHS). The central idea is 1 Regarding constraint programming, the Gecode solver implements CHB since version 5.1.0 released in April 2017 [ 23 ]. Similarly to SAT, the variables of a CSP instance are weighted according to ERWA in Gecode. to consider the history of constraint failures and favor the variables that often appear in recent failures. So, the con icts are dated and the constraints are weighted on the basis of the exponential recency weighted average. These weights are coupled to the variable domains to calculate the Con ict-History scores of the variables. 4.1

CHS Description

Formally, CHS maintains for each constraint cj a score q(cj ) which is initialized to 0 at the beginning of the search. If cj leads to a failure during the search because the domain of a variable in S(cj ) is emptied by propagation then q(cj ) is updated by the formula below derived from ERWA: q(cj ) = (1 ) q(cj ) + r(cj ) The parameter 0 < < 1 is the step-size and r(cj ) is the reward value. It de nes the importance given to the old value of q at the expense of the reward r. The value of decreases over time as it is applied in ERWA [ 24 ]. Indeed, starting from its initial value 0, decreases by 10 6 at each constraint failure to a minimum of 0:06. Decreasing the value amounts to giving more importance to the last value of q and considering that the values of q are more and more relevant as the search progresses.

The reward value r(cj ) is based on how recently cj occurred in con icts. The goal is to give a higher reward to constraints that fail regularly over short periods of time during the search space exploration. The reward value is calculated according to the formula: r(cj ) = #Conf licts 1 Conf lict(cj ) + 1 Initialized to 0, #Conf licts is the number of con icts which have occurred since the beginning of the search. Also initialized to 0 for each constraint cj 2 C, Conf lict(cj ) stores the last #Conf licts value where cj led to a failure. Once r(ci) and q(ci) are updated, #Conf licts is incremented by 1.

At this stage, we are able to de ne the Con ict-History score of the variables xi 2 X, which will be used in selecting the branching variable as follows: jDij CHS keeps the variable to branch on with the highest chv value. In this manner, CHS focuses branching on the variables with small size of domain while belonging to constraints which appear recently and repetitively in con icts.

One can observe that at the beginning of the search, all the variables have the same score equal to 0. To avoid random selection of the branching variable, we reformulate the calculation of chv as given below, where number close to 0. is a positive real jDij Thus, at the beginning of the search, the branching will be oriented according to the degree of the variables without having a negative in uence on the ERWAbased calculation later in the search. 4.2

CHS and Restarts

Nowadays, restart techniques are important for the e ciency of solving algorithms (see for example [ 13 ]). Restarts may allow to reduce the impact of irrelevant choices done during search according to heuristics such as variable selection.

As it will be detailed in the next section, CHS is integrated into CSP solving algorithms which include restarts. In the corresponding implementations, the Conf lict(cj ) value of each constraint cj is not reinitialized when a restart occurs. It is the same for q(cj ) (however, a smoothing may be applied and will be explained later). Keeping this information unchanged reinforces learning from the search history.

Concerning the step-size , which de nes the importance given to the old value of q(cj ) at the expense of the reward r(cj ), CHS reinitializes the step-size value to 0 at each restart. This may guide the search through di erent parts of the search space. 4.3

CHS and Smoothing

At each con ict and as in the dom=wdeg heuristic, CHS updates the chv score of one constraint at a time: the constraint cj which is used to wipe out the domain of a variable in S(cj ). As long as they do not appear in new con icts, some constraints can have their weights unchanged for several search steps. These constraints may have high scores while their importance does not seem high for the current part of the search. To avoid this situation, we propose to smooth the scores q(cj ) of all the constraints cj 2 C at each restart by the following formula: q(cj ) = q(cj )

0:995#Conflicts Conflict(cj) Hence, the scores of constraints are decayed according to the date of their last appearances in con icts. Decaying is also used in other heuristics such as ABS [ 18 ] for CSP and VSIDS [ 19 ] for SAT. However, it is applied to the score of the variables and not that of the constraints (or clauses). 5.1

Experimental Evaluation

Experimental Protocol

We consider 10,785 instances from the XCSP3 repository2, including notably structured instances and discarding fully random instances. This latter restriction is quite natural since adaptive heuristics aim to exploit the underlying structure of the instances to solve.

Regarding the solving step, we exploit MAC with restarts [ 14 ]. MAC uses a geometric restart strategy based on the number of backtracks with an initial cuto set to 100 and an increasing factor set to 1.1. In order to make the comparison fair, the lexicographic ordering is used for the choice of the next value to assign. Furthermore, no probing process is used for any heuristic for parameter tuning.

All the algorithms are written in C++. The experiments are performed on Dell PowerEdge M610 blade servers with Intel Xeon E5620 processors under Ubuntu 18.04. Each solving process is allocated a slot of 30 minutes and at most 12 GB of memory per instance. In the following tables, #solv denotes the number of solved instances by a given solver and time is the cumulative runtime. 5.2

Impact of CHS Settings

In this part, we assess the sensitivity of CHS with respect to the chosen values for or . First, we x to 10 4 (to start the search by considering the variable degrees then quickly exploit ERWA-based computation) and vary the value of 0 between 0.1 and 0.9 with a step of 0.1. Figure 1 presents the number of instances solved by MAC depending on the value of 0 and the corresponding cumulative runtime. We also provide the results of the Virtual Best Solver (VBS) when varying the value of .

se 9300 can it sn 9200 # 9600 9500 9400 9100 9000 8900 8800 #solved instances cumulative runtime 520 510 500 490 ) h ( 480 ite m n u 470 r 460 450 440 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 VBS 2 http://www.xcsp.org/series

We can observe that the value 0 = 0:4 allows MAC to solve more instances (9,525 solved instances with a cumulative solving time of 493 hours) than the other considered values. The worst case is 0 = 0:7 with 9,515 solved instances in 496 hours. This shows the robustness of CHS w.r.t. the parameter.

Regarding the VBS, we note that it can solve 64 additional instances than MAC+CHS when 0 = 0:4. Among these instances, some of them seem to be hard. Indeed, often, only one of the checked values of allows MAC to solve them and the required runtime generally exceeds several minutes. Therefore, a ner adjustment of the value of 0 or its adaptation to the treated instance would allow MAC+CHS to perform even better.

Now, we set 0 to 0.4 and evaluate di erent values of . From Table 1, the observations are similar to those presented previously, showing the robustness of CHS regarding . Also, it is interesting to highlight that MAC+CHS with = 0 solves 9,517 instances while it solves 9,525 instances if = 10 4. This illustrates the relevance of introducing in CHS.

Table 2 gives the results of MAC+CHS ( 0 = 0:4, = 10 4) with smoothing (+s) or not (-s) the constraint scores and/or with resetting (+r) or not (-r) the value of to 0:4 at each new restart. The observed behaviors clearly support the importance of these two operations for CHS. For example, MAC+CHS-s-r solves 43 less instances than MAC+CHS. Now, we compare CHS ( 0 = 0:4, = 10 4) to other search strategies: dom=wdeg, ABS and CHB as implemented in Gecode. For ABS, we x the decay parameter to 0.999 as in [ 18 ]. For CHB, we use the value parameters as given in [ 23 ]. We add a variant dom=wdeg+s which is dom=wdeg but the weights of constraints are smoothed exactly as in CHS.

From Table 3, it is clear that MAC with CHS performs better than with the other heuristics. Indeed, it solves 24 instances more than MAC+dom=wdeg, 49 instances more than MAC+ABS and 67 instances more than MAC+CHB. Interestingly, whatever the value of 0, MAC with CHS remains better than all its competitors. Indeed, the worst case is when 0 = 0:7 where MAC+CHS solves 9,515 instances. Moreover, the results obtained by MAC+CHB show that the calculation of weights by ERWA on the constraints (as done in CHS) is more relevant than its calculation on the variables (as done in CHB). Furthermore, the smoothing phase introduced in dom=wdeg allows MAC+dom=wdeg+s to reduce slightly the computation time when compared to MAC+dom=wdeg, while solving one less instance.

Table 4 provides the results of MAC variants on some instance families chosen form a representative panel of our benchmark and allow to show the di erent trends we observed. First, we can note that no heuristic is always better than the others. However, if we sort the heuristics with respect to the number of solved instances per family, CHS is ranked at the rst place for 88% of the 141 considered families, by performing better or similarly than the two other heuristics. This percentage exceeds respectively 93% and 99% if we consider the rst two places or the rst three places. Hence, CHS is clearly competitive. Also, one might think that dom=wdeg performs worse than ABS and CHB. This impression is explained by the fact that, when MAC+dom=wdeg is better on a given family, it solves only few additional instances. In contrast, when it is outperformed, this is done by several additional solved instances. Finally, if we compare the results on the instances labeled real-world in the XCSP3 repository, we observe that MAC with CHS solves more instances and performs faster, between 10% and 30%, than any other combination. 5.4

CHS and Tree-Decomposition

We now assess the behavior of CHS when the search is guided by a treedecomposition. Studying this question is quite natural since CHS aims at exploiting the structure of the instance, but in a way di erent from what the treedecomposition does. With this aim in view, we consider BTD-MAC+RST+Merge [ 10 ]. The parameters of BTD-MAC+RST+Merge are set like in [ 11 ] except the variable heuristic which can be one of the two best heuristics considered previously, namely dom=wdeg or CHS.

Like for MAC, the solving is more e cient with CHS than with dom=wdeg. Indeed, BTD-MAC+RST+Merge with CHS solves 9,525 instances (in 485 h) against 9,495 instances (in 501 h) for dom=wdeg. This observation shows that exploiting both CHS and tree-decomposition may be of interest and that these two strategies can be complementary. 6

Conclusion

We have proposed CHS, a new branching heuristic for CSP based on the search history and designed following techniques coming from reinforcement learning. The experimental results con rm the relevance of CHS which is competitive with the powerful heuristics dom=wdeg and ABS, when implemented in solvers based on MAC or tree-decomposition exploitation.

The experimental study suggests that the parameter value could be re ned. We will explore the possibility of de ning its value depending on the instance to be solved. Furthermore, similarly to the ABS heuristic, we will also consider to include information provided by ltering operations in CHS.

References

1. Bessiere , C. , Chmeiss , A. , Sas, L.: Neighborhood-based variable ordering heuristics for the constraint satisfaction problem . In: CP . pp. 565 { 569 ( 2001 )

2. Bessiere , C. , Regin , J.C. : MAC and Combined Heuristics: Two Reasons to Forsake FC (and CBJ?) on Hard Problems . In: CP. pp. 61 { 75 ( 1996 )

3. Boussemart , F. , Hemery , F. , Lecoutre , C. , Sa s, L.: Boosting systematic search by weighting constraints . In: ECAI . pp. 146 { 150 ( 2004 )

4. Brelaz , D. : New Methods to Color Vertices of a Graph . Communications of the ACM 22 ( 4 ), 251 { 256 ( 1979 )

5. Een , N. , Sorensson, N.: An Extensible SAT-solver . In: SAT . pp. 502 { 518 ( 2003 )

6. Geelen , P.A. : Dual viewpoint heuristics for binary constraint satisfaction problems . In: ECAI. pp. 31 { 35 ( 1992 )

7. Golomb , S.W. , Baumert , L.D.: Backtrack programming . Journal of the ACM 12 , 516 { 524 ( 1965 )

8. Haralick , R.M. , Elliot , G.L. : Increasing tree search e ciency for constraint satisfaction problems . AIJ 14 , 263 { 313 ( 1980 )

9. Hebrard , E. , Siala , M. : Explanation-based weighted degree . In: CPAIOR . pp. 167 { 175 ( 2017 )

10. Jegou , P. , Kanso , H. , Terrioux , C. : Towards a Dynamic Decomposition of CSPs with Separators of Bounded Size . In: CP. pp. 298 { 315 ( 2016 )

11. Jegou , P. , Kanso , H. , Terrioux" , C. : BTD and miniBTD . In: XCSP3 Competition ( 2017 )

12. Jegou , P. , Terrioux , C. : Hybrid backtracking bounded by tree-decomposition of constraint networks . AIJ 146 , 43 { 75 ( 2003 )

13. Lecoutre , C. , Sais , L. , Tabary , S. , Vidal , V. : Nogood recording from restarts . In: IJCAI . pp. 131 { 136 ( 2007 )

14. Lecoutre , C. , Sa s, L. , Tabary , S. , Vidal , V. : Recording and Minimizing Nogoods from Restarts . JSAT 1 ( 3-4 ), 147 { 167 ( 2007 )

15. Liang , J.H. , Ganesh , V. , Poupart , P. , Czarnecki , K. : Exponential Recency Weighted Average Branching Heuristic for SAT Solvers . In: AAAI. pp. 3434 { 3440 ( 2016 )

16. Liang , J.H. , Ganesh , V. , Poupart , P. , Czarnecki , K. : Learning Rate Based Branching Heuristic for SAT Solvers . In: SAT. pp. 123 { 140 ( 2016 )

17. Marques-Silva , J. , Sakallah , K.A. : Grasp: A search algorithm for propositional satis ability . IEEE Transactions on Computers 48 ( 5 ), 506 { 521 ( August 1999 )

18. Michel , L. , Hentenryck , P.V. : Activity-based search for black-box constraint programming solvers . In: CPAIOR . pp. 228 { 243 ( 2012 )

19. Moskewicz , M.W. , Madigan , C.F. , Zhao , Y. , Zhang , L. , Malik , S. : Cha : Engineering an E cient SAT Solver . In: DAC. pp. 530 { 535 ( 2001 )

20. Refalo , P. : Impact-based search strategies for constraint programming . In: CP . pp. 557 { 571 ( 2004 )

21. Rossi , F., van Beek , P. , Walsh , T. : Handbook of Constraint Programming , Foundations of Arti cial Intelligence , vol. 2 . Elsevier ( 2006 )

22. Sabin , D. , Freuder , E.C. : Contradicting Conventional Wisdom in Constraint Satisfaction . In: ECAI . pp. 125 { 129 ( 1994 )

23. Schulte , C. : Programming branchers . In: Schulte, C. , Tack , G. , Lagerkvist , M.Z. (eds.) Modeling and Programming with Gecode ( 2018 ), corresponds to Gecode 6.0.1

24. Sutton , R.S. , Barto , A.G. : Reinforcement Learning: An Introduction . MIT Press, Cambridge, MA, USA, 1st edn. ( 1998 )