Conflict Directed Backjumping for Max-CSPs

1 Introduction

In standard CSPs, when the algorithm detects that a solution to a given problem does not exist, the algorithm reports it and the search is terminated. In many cases, although a solution does not exist we wish to produce the best complete assignment, i.e. the assignment to the problem which includes the smallest number of conflicts. Such problems form the scope of Max-CSPs [Larrosa and Meseguer, 1996]. Max-CSPs are a special case of the more general Weighted CSPs (WCSPs) [Larrosa and Schiex, 2004] in which each constraint is assigned a weight which defines its cost if it is violated by a solution. The cost of a solution is the sum of the weights of all constraints violated by the solution (in Max-CSPs all weights are equal to 1). The requirement in solving WCSPs is to find the minimal cost (optimal) solution. WCSPs and Max-CSPs are therefore termed Constraint Optimization Problems.

∗The research was supported by the Lynn and William Frankel Center for Computer Science, and by the Paul Ivanier Center for Robotics.

In this paper we focus for simplicity on Max-CSPs. MaxCSP is an optimization problem with a search tree of bounded depth. Like other such optimization problems, the common choice for solving it is to use a Branch and Bound algorithm [Dechter, 2003]. In the last decade, various algorithms were developed for Max and Weighted CSPs [Wallace and Freuder, 1993; Larrosa and Meseguer, 1996; Larrosa et al., 1999; Larrosa and Schiex, 2004]. All of these algorithms are based on standard backtracking and gain their efficiency from the quality of the consistency maintenance procedure they use. In [Larrosa and Schiex, 2004], the authors present maintenance procedures of local consistency levels, NC* and AC*, which improve on former versions of Node-consistency and Arc-consistency. An improved result for Max-CSPs was presented in [Larrosa and Schiex, 2003]. This result was achieved by enforcing extended consistency which generates larger lower bounds.

The present paper improves on previous results by adding Conflict-directed Backjumping (CBJ) to the B&B algorithms presented in [Larrosa and Schiex, 2004] and in [Larrosa and Schiex, 2003]. Conflict-directed Backjumping (CBJ) [Prosser, 1993] is a method which is known to improve standard CSP algorithms [Dechter, 2003; Ginsberg, 1993; Kondrak and van Beek, 1997; Chen and van Beek, 2001]. In order to perform standard CBJ, the algorithm stores for each variable the set of assignments which caused the removal of values from its domain. When a domain empties, the algorithm backtracks to the last assignment in the corresponding conflict set [Chen and van Beek, 2001; Dechter, 2003].

One previous attempt at conflict directed B&B used reasoning about conflicts during each forward search step [Li and Williams, 2005]. Conflicts were used in order to guide the forward search away from infeasible and sub-optimal states. This is in contrast to the use of conflict reasoning for backjumping proposed in the present paper. Another attempt to combine conflict directed (intelligent) backtracking with B&B was reported for the Open-Shop problem [Gu´eret et al., 2000]. The algorithm proposed in [Gu´eret et al., 2000] is specific to the problem. Similarly to CBJ for standard CSPs, explanations for the removal of values from domains are recorded and used for resolving intelligently the backtrack destination.

Performing back-jumping for Max-CSPs is more complicated than for standard CSPs. In order to generate a consistent conflict set, all conflicts that have contributed to the current lower bound must be taken into consideration. Furthermore, additional conflicts with unassigned values of equal or higher costs must be added to the conflict set in order to achieve completeness.

The required information needed for the detection of the culprit variables that will be the targets for the algorithm backjumps is polynomial. The maintenance of the data structures does not require additional iterations of the algorithm.

The results presented in this paper show that as reported for standard CSPs by [Chen and van Beek, 2001], the improvement in run-time is dependent on the degree of the consistency maintenance procedure. However, the factor of improvement in the number of assignments when using CBJ is consistent and large.

Max-CSPs are presented in Section 2. A description of the standard B&B algorithm along with the maintenance procedures NC∗, AC∗ and FDAC is presented in Section 3. Section 4 presents the CBJ algorithm for B&B with NC∗, AC∗ and FDAC. An extensive experimental evaluation, of the contribution of conflict directed backjumping to B&B with NC∗, AC∗ and FDAC, is presented in Section 5. Our conclusions are in Section 6.

2 Max Constraint Satisfaction Problems

A Max - Constraint Satisfaction Problem (Max-CSP) is composed, like standard CSP, of a set of n variables X1,X2, ...,Xn. Each variable can be assigned a single value from a discrete finite domain {D1, D2, ..., Dn} respectively. Similarly to former studies of Max-CSPs [Larrosa and Meseguer, 1996; Larrosa et al., 1999; Larrosa and Schiex, 2003], we assume that all constraints are binary. A binary constraint Rij between any two variables Xj and Xi is a subset of the Cartesian Product of their domains; Rij ⊆ Dj ×Di.

An assignment (or a label) is a pair 〈var, val〉, where var is a variable and val is a value from var's domain that is assigned to it. A partial solution is a set of assignments of values to variables. The cost of a partial solution in a MaxCSP is the number of constraints violated by it (conflicts). An optimal solution to a Max-CSP is a partial solution that includes all variables and which includes a minimal number of unsatisfied constraints, i.e. a solution with a minimal cost.

3 The Branch and Bound algorithm

Optimization problems with a finite search-space are often solved by a Branch and Bound (B&B) algorithm. Both Weighted CSPs and Max-CSPs fall into this category.

The B&B algorithm is presented in Figure 1. The general structure of the algorithm is different than its recursive presentation in [Larrosa and Schiex, 2004]. In order to be able to perform backjumping, we need an iterative formulation (cf. [Prosser, 1993]). We use an array of states which hold for each successful assignment the state of the algorithm before it was performed. After each backtrack the current

B&B

1. current state ← initial state; 2. CPS ← empty assignment; 3. i ← 0; 4. while(i ≥ 0) 5. if(i = n) 6. upper bound ← lower bound; 7. i ← i - 1; 8. else foreach (a ∈ Di) 9. temp state ← current state; 10. update state(temp state, i, a); 11. if(local consistent(temp state)) 12. states[i] ← current state; 13. current state ← temp state; 14. i ← i + 1; 15. i ←find culprit variable(); 16. current state ← states[i]; update state(temp state, i, val) 17. add (i, val) to temp state.CPS; 18. temp state.CPS.cost ← temp state.CPS.cost + cost(i, val); 19. for j ← (i +1) to (n-1) 20. foreach (a ∈ temp state.Dj) 21. if(conflicts(〈i, val〉, 〈j, a〉)) 22. cost(a, i) ← cost(a, i) + 1;

state of the algorithm will be set to the state which was stored before the culprit assignment was performed. The space complexity stays the same as in the recursive procedure case, i.e. larger than a single state by a factor of n. For simplicity of presentation we use a fixed order of variables and the function find culprit variable simply returns i - 1.

The naive and exhaustive B&B algorithm can be improved by increasing the level of the maintained local consistency. As a result, the value of the lower bound of a current partial solution is increased. After each assignment, the algorithm performs a consistency maintenance procedure that updates the costs of potential future assignments and increases its chance to detect early a need to backtrack. Three of the most successful consistency check functions are described next.

3.1 Node Consistency and NC*

Node Consistency is a very standard consistency maintenance method (analogous to Forward-checking in standard CSPs) [Dechter, 2003]. The main idea is to ensure that in the domains of each of the unassigned variables there is at least one value which is consistent with the current partial solution (CPS). For each value in a domain of an unassigned variable, one must determine whether assigning it will increase the lower bound beyond the limit of the upper bound. To this end, the algorithm maintains for every value a cost which is its number of conflicts with assignments in the CPS. After each assignment, the costs of all values in domains of unassigned variables are updated. When the sum of a value's cost and the cost of the CPS is higher or equal to the upper bound, the value is eliminated from the variable's domain. An empty domain triggers a backtrack.

The down side of this method in Max-CSPs is that the number of conflicts counted and stored as the value's cost, does not contribute to the global lower bound and it affects the search only if it exceeds the upper bound. In [Larrosa

NC*(i) 1. for j ← (i +1) to (n-1) 2. cj ←min cost(Dj); 3. foreach (a ∈ Dj ) 4. a.cost ← a.cost - cj ; 5. Cφ ←Cφ + cj; 6. lower bound ←CPS.cost +Cφ; 7. for j ← (i +1) to (n-1) 8. foreach (a ∈ Dj ) 9. if(a.cost + lower bound ≥ upper bound) 10. Dj ←Dj \ a; 11. return (lower bound < upper bound);

and Schiex, 2004], the authors suggest an improved version of Node Consistency they term NC*. In NC* the algorithm maintains a global cost Cφ which is initially zero. After every assignment, all costs of all values are updated as in standard NC. Then, for each variable, the minimal cost of all values in its domain, ci, is added to Cφ and all value costs are decreased by ci. This means that after the method is completed in every step, the domain of every unassigned variable includes one value whose cost is zero. The global lower bound is calculated as the sum of the CPS's cost and Cφ.

Any value whose lower bound, i.e. the sum of the CPS's cost, Cφ and its own cost, exceeds the limit of the upper bound, is removed from the variable's domain as in standard NC [Larrosa and Schiex, 2004].

The NC∗ consistency maintenance function is presented in Figure 2.

3.2 Arc Consistency and AC*

A stronger consistency maintenance procedure which is known to be effective for CSPs is Arc Consistency (AC) [Bessiere and Regin, 1995].

In Max-CSPs, a form of Arc-Consistency is used to project costs of conflicts between unassigned variables [Larrosa and Meseguer, 1996; Larrosa et al., 1999; Larrosa and Schiex, 2003; 2004]. AC∗ combines the advantages of AC and NC∗. After performing AC, the updated cost of the values are used by the NC∗ procedure to increase the global cost Cφ. Values are removed as in NC∗ and their removal initiates the rechecking of AC. The system is said to be AC∗ if it is both AC and NC∗ (i.e. each domain has a value with a zero cost) [Larrosa and Schiex, 2004].

3.3 Full Directed Arc Consistency

The FDAC consistency method enforces a stronger version of Arc-Consistency than AC∗ (cf. [Larrosa and Schiex, 2003]). Consider a CSP with an order on its unassigned variables. If for each value valik of variable Vi, in every domain of an unassigned variable Vj which is placed after Vi in the order, a value valjs has a cost of zero and there is no binary constraint between valik and valjs , we say that the CSP is in a DAC state. A CSP is in a FDAC state if it is both DAC and AC∗. 1

1 The code for the AC∗ and FDAC procedures is not used in this paper therefore the reader is referred to [Larrosa and Schiex, 2003; 2004].

For a detailed description of FDAC and demonstrations of how FDAC increases the lower bound, the reader is referred to [Larrosa and Schiex, 2003].

4 Branch and Bound with CBJ

The use of Backjumping in standard CSP search is known to improve the run-time performance of the search by a large factor [Prosser, 1993; Kondrak and van Beek, 1997; Dechter and Frost, 2002; Chen and van Beek, 2001]. Conflict directed Backjumping (CBJ) maintains a set of conflicts for each variable, which includes the assignments that caused a removal of a value from the variable's domain. When a backtrack operation is performed, the variable that is selected as the target, is the last variable in the conflict set of the backtracking variable. In order to keep the algorithm complete during backjumping, the conflict set of the target variable, is updated with the union of its conflict set and the conflict set of the backtracking variable [Prosser, 1993].

The data structure of conflict sets which was described above for CBJ on standard CSPs can be used for the B&B algorithm for solving Max-CSPs. However, additional aspects must be taken into consideration for the case of MaxCSPs.

In the description of the creation and maintenance of a consistent conflict set in a B&B algorithm the following definitions are used:

Definition 1 A global conflict set (GCS) is the set of assignments whose replacement can decrease the lower bound.

Definition 2 The current cost of a variable is the cost of its assigned value, in the case of an assigned variable, and the minimal cost of a value in its current domain in the case of an unassigned variable.

Definition 3 A conflict list of value vij ∈ Di, is the ordered list of assignments of variables in the current partial solution, which were assigned before variable i, and which conflict with vij .

Definition 4 The conflict set of variable Xi with cost ci is the union of the first (most recent) ci assignments in each of the conflict lists of all values of Xi (if the conflict list of a value is shorter than ci then all its assignments are included in the variables' conflict set).

In the case of simple B&B, the global conflict set is the union of all the conflict sets of all assigned variables. Values are always assigned using the min-cost heuristic i.e. the next value to be assigned is the value with the smallest cost in the variable's current domain. Before assigning a variable the cost of each value is calculated by counting the number of conflicts it has with the current partial solution. Next, the variable's current cost is determined to be the lowest cost among the values in its current domain. As a result, the variable's conflict set is generated. The reason for the need to add the conflicts of all values to a variable's conflict set and not just the conflicts of the assigned value, is that all the possibilities for decreasing the minimal number of conflicts of any of the variables' values must be explored. Therefore,

update state(i, val) 1. add (i, val) to CPS; 2. CPS.cost ←CPS.cost + cost(i, val); 3. foreach(a ∈ Di) 4. for 1 to val.cost 5. GCS ←GCS ∪ first element in a.conflict list; 6. remove first element from a.conflict list 7. for j ← (i +1) to (n-1) 8. foreach (a ∈ Dj ) 9. if(conflicts(〈i, val〉, 〈j, a〉) 10. a.cost ← a.cost + 1; 11. a.conflict list ← a.conflict list ∪ (i, val);

find culprit variable(i)

12. if(GCS = φ) 13. return -1; 14. culprit ← latest assignment in GCS; 15. GCS ←GCS \ culprit;

1. return culprit;

Figure 4: A conflict set of an assigned variable

the latest assignment that can be replaced, and possibly decrease the cost of one of the variables values to be smaller than the variable's current cost must be considered.

Figure 3 presents the changes needed for adding CBJ to standard B&B. After a successful assignment is added to the CPS, its cost is added to the cost of the CPS (lines 1,2). Then, the added cost, val.cost is used to determine which assignments are added to the global conflict set (GCS). For each of the values in the domain of variable i, the first val.cost assignments are removed and added to the GCS (lines 3-6). As a result, when performing a backjump, all that is left for function find culprit variable to do is to return the latest assignment (the one with the highest variable index) in the GCS (lines 14-16). In case the GCS is empty, function find culprit variable returns -1 and as a result, terminates the algorithm (lines 12,13).

The space complexity of the overhead needed to perform CBJ in B&B is simple to bound from above. For a CSP with n variables and d values in each domain, the worst case is that for each value the algorithm holds a list of O(n) assignments. This bounds the space complexity of the algorithm's state by O(n2d). Since we hold up to n states, the overall space used is bounded by O(n3d).

Figure 4 presents the state of three variables which are included in the current partial solution. Variables X1, X2 and X3 were assigned values v1, v2 and v1 respectively. All costs of all values of variable X3 are 1. The conflict set of variable X3 includes the assignments of X1 and X2 even though its assigned value is not in conflict with the assignment of X2.

However, replacing the current assignment of X2 can lower the cost of value v2 of variable X3.

4.1 Node Consistency with CBJ

In order to perform CBJ in a B&B algorithm that uses node consistency maintenance, the conflict sets of unassigned variables must be maintained. To achieve this goal, for every value of a future variable a conflict list is initialized and maintained. The conflict list includes all the assignments in the CPS which conflict with the corresponding value. The length of the conflict list is equal to the cost of the value. Whenever NC∗ adds the cost ci of the value with minimal cost in the domain of Xi to the global cost Cφ, the first ci assignments in each of the conflict lists of Xi's values are added to the global conflict set and removed from the value's conflict lists. This includes all the values of Xi including the values removed from its domain. Backtracking to the head of their list can cause the return of removed values to the variables current domain. This means that after each run of the NC∗ procedure, the global conflict set includes the union of the conflict sets of all assigned and unassigned variables.

Figure 5 presents the state of an unassigned variable Xi. The CPS includes the assignments of three variables as in the example in Figure 4. Values v1 and v3 of variable Xi are both in conflict only with the assignment of variable X1. Value v2 of Xi is in conflict with the assignments of X2 and X3. Xi's cost is 1 since that is the minimal cost of its values. Its conflict set includes the assignments of X1 since it is the first in the conflict list of v1 and v3, and X2 since it is the first in the conflict list of v2. After the NC∗ procedure, Cφ will be incremented by one and the assignments of X1 and X2 will be added to the global conflict set.

Figure 6 presents the changes in NC∗ that are required for performing CBJ. For each value whose cost is decreased by the minimal cost of the variable, cj, the first cj assignments in its conflict list are removed and added to the global conflict set (lines 5-7). Note that the revised procedure uses the conflict lists of removed values as well as of remaining values. For each domain Di an additional set, ˆ Di is maintained, which holds the values that were removed fromDi.

4.2 AC* and FDACwith CBJ

Adding CBJ to a B&B algorithm that includes arcconsistency is very similar to the case of node consistency. Whenever a minimum cost of a future variable is added to the global cost Cφ, the prefixes of all of its values' conflict lists are added to the global conflict set. However, in AC∗, costs

NC* BJ(i) 1. for j ← (i +1) to (n-1) 2. cj ←min cost(Dj); 3. foreach (a ∈ (Dj ∪ ˆ Dj )) 4. a.cost ← a.cost - cj ; 5. for 1 to cj 6. GCS ←GCS∪ first element in a.conflict list; 7. remove first element from a.conflict list; 8. Cφ ←Cφ + cj; 9. lower bound ←CPS.cost +Cφ; 10. for j ← (i +1) to (n-1) 11. foreach (a ∈ Dj ) 12. if(a.cost + lower bound ≥ upper bound) 13. ˆ Dj ← ˆ Dj ∪ a; 14. Dj ←Dj \ a; 15. return (lower bound < upper bound);

of values can be incremented by conflicts with other unassigned values. As a result, the cost of a variable may be larger than the length of its conflict list. In order to find the right conflict set in this case one must keep in mind that except for an empty CPS, a cost of a value vk of variable Xi is increased due to arc-consistency only if there was a removal of a value which is not in conflict with vk, in some other unassigned variable Xj. This means that a removal of the last assignment in the CPS would return the value which is not in conflict with vk, to the domain of Xj. Whenever a cost of a value is raised by arc-consistency, the last assignment in the CPS must be added to the end of the value's conflict list. This addition restores the correlation between the length of the conflict list and the cost of the value. The variable's conflict set and the global conflict set can be generated in the same way as for NC∗.

Maintaining a consistent conflict set in FDAC is somewhat similar to AC∗. Whenever a cost of a value is extended to a binary constraint, its cost is decreased and its conflict list is shortened. When a binary constraint is projected on a value's cost, the cost is increased and the last assignment in the CPS is added to its conflict list. Caution must be taken when performing the assignment since the constant change in the cost of values may interfere with the min-cost order of selecting values. A simple way to avoid this problem is to maintain for each value a different cost which we term priority cost. The priority cost is updated whenever the value's cost is updated except for updates performed by the DAC procedure. When we choose the next value to be assigned we break ties of costs using the value of the priority cost.

5 Experimental Evaluation

The common approach in evaluating the performance of CSP algorithms is to measure time in logic steps to eliminate implementation and technical parameters from affecting the results. Two measures of performance are used by the present evaluation. The total number of assignments and cpu-time. This is in accordance with former work on Max-CSP algorithms [Larrosa and Schiex, 2003; 2004].

Experiments were conducted on random CSPs of n variables, k values in each domain, a constraint density of p1

and tightness p2 (which are commonly used in experimental evaluations of Max-CSP algorithms [Larrosa and Meseguer, 1996; Larrosa et al., 1999; Larrosa and Schiex, 2004]). In all of the experiments the Max-CSPs included 10 variables (n = 10) and 10 values for each variable (k = 10). Two values of constraint density p1 = 0.4 and p1 = 0.9 were used to generate the Max-CSPs. The tightness value p2, was varied between 0.7 and 0.98, since the hardest instances of Max-CSPs are for high p2 [Larrosa and Meseguer, 1996; Larrosa et al., 1999]. For each pair of fixed density and tightness (p1, p2), 50 different random problems were solved by each algorithm and the results presented are an average of these 50 runs.

In order to evaluate the contribution of CBJ to B&B algorithms using consistency maintenance procedures, the B&B algorithm with NC∗, AC∗ and FDAC was implemented. The results presented show the performance of these algorithms with and without CBJ. The NC∗ procedure was tested only for low density problems p1 = 0.4, since it does not complete in a reasonable time for p1 = 0.9.

The left hand side (LHS) of Figure 7 presents the number of assignments performed by NC* and NC* CBJ. For the hardest instances, where p2 is higher than 0.9, NC* CBJ outperforms NC* by a factor of between 3 at p2 = 0.92 and 2 at p2 = 0.99. The right hand side (RHS) of Figure 7 shows similar results for cpu-time.

The LHS of Figure 8 presents the number of assignments performed by AC* and AC* CBJ. For the hardest instances, where p2 is higher than 0.9, AC* CBJ outperforms AC* by a factor of 2. The RHS of Figure 8 presents the result in cpu-time which are similar but the difference is smaller than for the number of assignments. Note that both performance measures decrease for p2 values above 0.98 for AC* CBJ. This demonstrates a phase transition [Larrosa and Meseguer, 1996; Larrosa and Schiex, 2004].

Figure 9 presents similar results for the AC* algorithm solving high density Max-CSPs (p1 = 0.9). The factor of improvement is similar to the low density experiments for both measures.

The LHS of Figure 10 presents the number of assignments performed by FDAC and FDAC CBJ. The difference in the number of assignments between the conflict-directed backjumping version and the standard version is much larger than for the case of NC* and AC*. However, the difference in cputime, presented on the RHS of Figure 10, is smaller than for the previous procedures. These differences are also presented for high density Max-CSPs in Figure 11.

The big difference between the results in number of assignments and in cpu-time for deeper look-ahead algorithms can be explained by the large effort that is spent in FDAC for detecting conflicts and pruning during the first steps of the algorithms run. For deeper look-ahead, the backjumping method avoids assignment attempts which require a small amount of computation. The main effort having been made during the assignments of the first variables of the CSP which are performed similarly, in both versions.

6 Conclusions

Branch and Bound is the most common algorithm used for solving optimization problems with a finite search space (such as Max-CSPs). Former studies improved the results of standard Branch and Bound algorithms by improving the consistency maintenance procedure they used [Wallace and Freuder, 1993; Larrosa and Meseguer, 1996; Larrosa et al., 1999; Larrosa and Schiex, 2003; 2004]. In the present study we adjusted conflict directed backjumping (CBJ), which is a common technique for standard CSP search [Prosser, 1993; Kondrak and van Beek, 1997], to Branch and Bound with extended consistency maintenance procedures. The results presented in Section 5 show that CBJ improves the performance of all versions of the B&B algorithm. The factor of improvement in the number of assignments when using conflict directed backjumping is consistent and large. The factor of improvement in run-time is dependent on the consistency maintenance procedure used (as reported for standard CSPs by [Chen and van Beek, 2001]). The factor of improvement does not decrease (and even grows) for random problems with higher density.

Figure 11: Assignments and Run-time of FDAC and FDAC CBJ (p1 = 0.9)