Partial lazy forward checking

Partial Lazy Forward Checking * Javier Larrosa1 and Pedro Meseguer2 1Universitat Politècnica de Catalunya, Dep. Llenguatges i Sistemes Informàtics Jordi Girona Salgado 1-3, 08034 Barcelona, SPAIN E-mail: [email protected] 2Institut d'Investigació en Intel.ligència Artificial, CSIC Campus UAB, 08193 Bellaterra, SPAIN. E-mail: [email protected] Abstract. Partial forward checking (PFC) may perform more consistency checks than really needed to detect dead-ends in MAX-CSP. After analyzing PFC, we have identified four causes of redundant check computation: (a) unnecessary lookahead when detecting an empty domain, (b) not always using the better bounds for future value pruning, (c) computing in advance inconsistency counts, and (d) lookahead is performed on the whole set of future variables. We present the partial lazy forward checking (PLFC) algorithm, which follows a lazy approach delaying as much as possible inconsistency count computation, keeping updated the contribution of future variables to the lower bound. This algorithm avoids the causes of redundant checks identified for PFC. It can be easily combined with DACs, producing the PLFC-DAC algorithm. Empirical results on random problems show that PLFC-DAC outperforms previous algorithms in both consistency checks and CPU time. 1 Introduction Constraint satisfaction problems (CSP) consider the assignment of values to variables under a set of constraints. A solution is a total assignment satisfying every constraint. If such assignment does not exist, the problem is overconstrained, and it may be of interest to find a total assignment satisfying as many constraints as possible. This problem is called the maximal constraint satisfaction problem (MAX-CSP), and a solution is a total assignment satisfying the maximum number of constraints. MAXCSP is of interest in several areas of application [Fox, 87; Feldman and Golumbic, 90; Bakker et al., 93]. Partial forward checking (PFC)1 is one of the best algorithms for MAX-CSP [Freuder and Wallace, 92]. It is a branch and bound algorithm including forward checking in order to anticipate dead-ends before they actually occur. To detect deadends, PFC computes a lower bound of the number of unsatisfied constraints from (i) the set of past variables, and (ii) the effect of past variables on future ones, by using inconsistency counts (IC). Recently, this lower bound has been improved by including * This research has been supported by the Spanish CICYT under the project #TIC96-0721C02-02. 1 In [Freuder and Wallace, 92] several versions of partial forward checking are presented. We use here as PFC their P-EFC3 algorithm. unsatisfied constraints from the set of future variables. This has been implemented using directed arc-consistency counts (DAC) [Wallace, 94], and the reported empirical results show a clear improvement in performance with respect to pure PFC. DAC are computed in a preprocessing step, which is later followed by PFC for variable instantiation. DAC usage has been enhanced by [Larrosa and Meseguer, 96] in their PFC-DAC algorithm2, which has a better performance than the initial combination of PFC and DAC proposed by [Wallace, 94]. In this paper, we show that the PFC greedy strategy of performing lookahead on every future variable may require more consistency checks than really needed to detect dead-ends. A careful analysis of PFC behaviour has allowed us to identify the following causes of redundant consistency checks: (a) PFC may do unnecessary lookahead when detecting an empty domain, performing checks that are never used, (b) PFC does not always use the better bounds for future value pruning, which may cause to collect more inconsistencies than really needed and therefore, it may require the computation of an extra number of consistency checks, (c) computing in advance inconsistency counts may cause more checks than really needed to prune a value of the current variable, and (d) lookahead is performed on the whole set of future variables, possibly doing more work than really needed to prune a value of the current variable. Based on this analysis we take a lazy approach that essentially consists on delaying as much as possible the IC computation, while keeping updated the contribution of future variables to the lower bound. This lazy strategy is further developed in the following points: (α) future domains are not pruned in advance, (β) the lowest amount of lookahead is done on future domains, to compute the minimal contribution of future variables to the lower bound, and (γ) IC updating and lookahead can be stopped prior completion. Following these points we have developed the partial lazy forward checking algorithm (PLFC). Since future domains are not pruned and ICs are not completely updated, PLFC cannot compute without an extra cost some dynamic variable ordering heuristics (minimum domain or largest mean of ICs). The lazy approach can be easily combined with DACs, just in the same way it was combined with the greedy algorithm, producing the PLFC-DAC algorithm. This combination is particularly adequate: because of DAC usage, this algorithm requires static variable order, so the inability of PLFC to compute some dynamic variable ordering heuristics is not really a drawback, while keeping the advantages caused by DACs for a better lower bound. This paper is organized as follows. In Section 2 we present related approaches to the paper topic. In Section 3 we provide some preliminaries and definitions required in the rest of the paper. In Section 4, we analyze the behaviour of PFC, showing that it may perform more consistency checks than required, and we present our lazy approach to PFC, the PLFC algorithm. This algorithm is combined with the DAC usage, producing the PLFC-DAC algorithm. In Section 5, we give empirical results of PLFC-DAC on random problems, showing a clear performance improvement in both 2 In [Larrosa and Meseguer, 96] this algorithm was called P-EFC3+DAC2. For simplicity reasons, we refer it as PFC-DAC from now on. number of consistency checks and CPU time with respect to PFC-DAC. Finally, in Section 6 we summarize the conclusions of this work. 2 Related Work The simplest algorithm for MAX-CSP is depth-first branch and bound, which traverses completely the whole search tree looking for the leaf node violating a minimal number of constraints. In terms of variable assignments, an internal node represents a partial assignment while a leaf node represents a total one. The distance of a node is the number of constraints violated by its assignment. At each internal node, the algorithm computes a lower bound of the distance of any leaf node below the current one. It also keeps track of the best leaf node (complete assignment violating less constraints) found so far, and its best distance is an upper bound of the allowable distance of any future leaf node. When the lower bound is greater than or equal to the upper bound, the current node (and all its successors) can be pruned because no leaf node below the current one will improve the best distance already found. This basic algorithm can be enhanced with more sophisticated strategies, and in particular we consider partial forward checking (PFC), which evaluates the impact of the current partial assignment on future variables computing ICs, which allows PFC to improve the lower bound. For a detailed description of other algorithms, see [Freuder and Wallace, 92]. Regarding dynamic variable ordering with PFC, variables may ordered either by the largest mean of inconsistency counts in their domains or by minimum domain size, and dynamic value ordering considers values by increasing IC [Freuder and Wallace, 92]. Two heuristics for dynamic variable and value ordering are given in [Larrosa and Meseguer, 95]. Other static variable ordering heuristics can be found in [Wallace and Freuder, 93]. DAC usage has been an important step to increase the lower bound [Wallace, 94; Larrosa and Meseguer, 96; Wallace, 96]. Another way to improve the lower bound is russian doll search [Verfaille et al, 96], where the whole problem is substituted by n nested subproblems such that the solution of the i-th subproblem can be used as the starting lower bound for the i+1th subproblem. Several approaches have tried to improve the upper bound at early search states by heuristic repair [Wallace, 96] and by stochastic methods [Cabon et al, 96]. The idea of lazy evaluation in not new in constraint satisfaction, although it has not been fully exploited. Regarding forward checking (FC), several researchers have realized that it performs more lookahead than needed to detect empty domains [Zweben and Eskey, 89; Dent and Mercer, 94; Bacchus and Grove, 95]. FC checks every feasible value of every future domain, while it would be enough to stop checking a future domain as soon as one consistent value has been found. The lazy FC approach, called minimal forward checking, has proved to save from 10% to 30% of consistency checks solving several problem classes [Bacchus and Grove, 95]. Regarding arc consistency (AC), a similar situation has been reported by [Schiex et al, 96]: AC algorithms perform more checking than needed to detect empty domains. 3 Preliminaries A discrete binary CSP is defined by a finite set of variables {Xi} taking values on discrete and finite domains {Di} under a set of binary constraints {Rij}. A constraint Rij is a subset of Di×Dj, containing the permitted values for Xi and Xj. The number of variables is n and, without loss of generality, we will assume a common domain D for all variables, m being its cardinality. A global solution of the CSP is an assignment of values to variables satisfying every constraint. If no solution exists the CSP is overconstrained; in this case we are interested in finding solutions satisfying a maximum number of constraints. This problem is usually referred as MAX-CSP. Partial forward checking (PFC) is an efficient algorithm to solve MAX-CSP [Freuder and Wallace, 92]. It is a forward checking algorithm over the branch and bound schema and its code appears in Figure 1 (assuming for simplicity of presentation that variables are assigned in lexicographical order). At a given node, we denote by P and F the sets of past and future variables respectively. PFC keeps for every feasible value l of every unassigned variable Xi, the inconsistency count icil which records the number of inconsistencies that l has with the assignments of past variables. If Xi is the current variable and value l is assigned to it, the lower bound of the current partial assignment is increased in icil, as the number of inconsistencies between Xi and P. The sum ∑ j∈F  mink {icjk} is a lower bound of the number of inconsistencies that will necessarily occur when every future variable is instanciated, so it can included to compute the lower bound of the current partial assignment (lines 13 and 32). In addition, if Xi is a future variable, value l can be pruned if the current distance plus icil plus the sum of mink {icjk} of other future variables is not lower than the best distance (lines 21 and 24). This value is called the lower bound associated with l. Finally, values can be heuristically ordered by increasing ICs. PFC has been enhanced with the inclusion of DACs: given a static variable ordering, the DAC associated to a value l of a variable Xi,dacil, is the number of variables which are arc-inconsistent with value l for Xi and appear after Xi in the ordering [Wallace, 94]. ICs and DACs were first combined to improve lower bound computation and better value pruning in [Wallace, 94] and later in [Larrosa and Meseguer, 96]. If Xi is the current variable and value l is assigned to it, the lower bound of the current partial assignment is increased in icil + dacil, as the number of inconsistencies between Xi and P plus the number of inconsistencies that necessarily will appear between Xi and F when extending the current partial assignment into a total one. The sum ∑ j∈F  mink {icjk +dacjk} is a lower bound of the number of inconsistencies that will necessarily occur when every future variable is instanciated, so it can be included to compute the lower bound of the current partial assignment. In addition, if Xi is a future variable, value l can be pruned if the current distance plus icil + dacil plus the sum of mink {icjk +dacjk} of other future variables is not lower than the best distance. This value is called the lower bound associated with l(when DACs are used). Finally, values can be heuristically ordered by increasing procedure PFC (current_solution,next_variable,distance) 1 Xi := next-variable; 2 values := sort-values(Xi); 3 while values ≠ Ø do 4 l := first(values); 5 values := values - l; 6 if (feasible(Xi,l)) then 7 new_distance := distance + icil; 8 if (i = n) then 9 best_distance := new_distance; 10 best_solution := current_solution + (Xi,l); 11 else 12 if (look_ahead(Xi,l)) then 13 if (new_distance + ∑ j>i  mink{icjk} < best_distance) then PFC(current_solution+(Xi,l),Xi+1,new_distance); 14 endif 15 endif 16 endif 17 endif 18 endwhile endprocedure function look_ahead (Xi,l) 19 for j := i+1 to n do 20 forall k∈Feasibles do 21 if (new_distance + icjk +∑ p∈F-j minq{icpq} ≥ best_distance) then prune(Xj,k) 22 elsif (inconsistent(Xi,l,Xj,k)) then 23 icjk := icjk + 1; 24 if (new_distance + icjk +∑ p∈F-j minq{icpq} ≥ best_distance) then prune(Xj,k) 25 endif 26 endif 27 endforall 28 if (empty domain(Xj)) then return false endif 29 endfor 30 return true endfunction function feasible (Xi,l) 31 return (distance + icil +∑ j>i  mink{icjk} < best_distance) endfunction Figure 1. The PFC algorithm. IC+DACs. The PFC-DAC algorithm [Larrosa and Meseguer, 96] can be easily obtained from PFC substituting lines 13, 21, 24 and 31 of Figure 1 by the following lines: 13 if (new_distance + ∑ j∈F mink{icjk+dacjk} < best_distance) 21 if (new_distance + dacil + icjk + dacjk +∑ p∈F-j minq{icpq+dacpq} ≥ best_distance) then prune(Xj,k) 24 if (new_distance + icjk + dacjk + ∑ p∈F-j minq{icpq+dacpq} ≥ best_distance) then prune(Xj,k) 31 return (distance+icil+dacil +∑ j∈F  mink{icjk+dacjk} < best_distance) 4 PFC and Lazy Evaluation The idea of lazy evaluation in PFC consists on delaying as much as possible the computation of inconsistency counts, producing as an inmediate consequence the delay of future value pruning. Although this may seem counterintuitive for a forward checking algorithm based on lookahead, in the following we will show that delaying inconsistency count computation may cause a decrement in the number of consistency checks performed by the algorithm, without decreasing its pruning capability. In the following, we analyze the PFC greedy behaviour to identify those situations where it may perform more consistency checks than needed. 4.1 PFC Analysis PFC tries to anticipate pruning of future values as much as possible. For this reason, the pruning condition in future domains is checked each time the look_ahead function is called and, necessarily, inconsistency counts are continuously updated. We analyze the two situations where value pruning occurs: 1. Early pruning (lines 21 and 24, Figure 1). Value l of future variable Xi is early pruned as a side-effect of the look_ahead function, because the lower bound associated with l is greater than or equal to the current upper bound. In this situation, there are the following independent sources of redundant consistency check computation: 1.1. If the domain of future variable Xi becomes empty after pruning value l, the lookahead performed from the current variable on any other future variable different from Xi is useless. Therefore, those consistency checks performed by this lookahead are redundant. 1.2. If the domain of future variable Xi does not become empty after pruning value l, there are two further situations: 1.2.1. The lower bound associated with value l at the current node, denoted as node A, is as follows, distance(A) +icil(A) + ∑ j∈F(A)-i  mink {icjk} Let us assume that the evaluation of the pruning condition for value l is delayed to a future node in which Xi is the current variable. Calling it node B, the lower bound associated with l at B is as follows, distance(B) +icil(B) + ∑ j∈F(B)  mink {icjk} At node A, the contribution of each future variable between the current one and Xi is mink {icjk}. At node B, the contributions of these variables are greater than or equal to the corresponding contributions at node A, and they are included in distance(B), since these variables have become past variables at node B. At node A, the contribution of each future variable after Xi is mink {icjk}. At node B, the contributions of these variables are greater than or equal to the corresponding contributions at node A, since their mink {icjk} could have increased. Therefore, the following inequality holds, distance(A) + ∑ j∈F(A)-i  mink {icjk} ≤distance(B) + ∑ j∈F(B)  mink {icjk} that is, the contribution of every variable but Xi to the lower bound associated with l at node Bis greater than or equal to the same contribution at node A. Therefore, the required contribution from icil to satisfy the pruning condition of value lat node B is lower than or equal to the same contribution that is required at node A. In other words, delaying pruning evaluation until node B may require collecting a lower (and never higher) number of inconsistencies caused by l than at node A.Ificil is computed at node B, checking that the pruning condition is satisfied will require a lower (and never higher) number of consistency checks than if icil is computed at node A. 1.2.2. Value lhas been pruned at node A using the current upper bound. However, if l pruning is delayed to node B, in which Xi is the current variable, a better upper bound may be available. The upper bound at node B will be lower than or equal to the upper bound at node A. This will cause a less demanding pruning condition, able to be satisfied with less consistency checks than required to prune l at node A. Analyses 1.2.1 and 1.2.2 are independent and complementary. Pruning delay may decrease the number of consistency checks needed to compute inconsistency counts because other contributions to the lower bound may increase (1.2.1). In addition, pruning delay may also decrease the number of consistency checks needed to compute inconsistency counts, because the upper bound has decreased and the pruning condition is easier to satisfy (1.2.2). Considering both analyses simultaneously magnifies their effects in consistency checks decrement. As conclusion, early pruning does not always use the better bounds to minimize the number of checks, and it may perform more checks that required. 0 0.02 0.04 0.06 0.08 CPU time (sec.) 0 1 2 3 4 CPU time (sec.) 0.5 0.6 0.7 0.8 0.9 1 P2 PFC-DAC PLFC-DAC p1= 35/45 p1= 15/45 0 0.25 0.5 0.75 1 0 5 10 15 20 25 30 0.5 0.6 0.7 0.8 0.9 1 P2 p1= 25/45 p1= 45/45 Figure 5. CPU time on the <10,10> random problem class. 0 0.02 0.04 0.06 0.08 CPU time (sec.) 0 2 4 6 8 CPU time (sec.) 0.4 0.5 0.6 0.7 0.8 0.9 1 P2 PFC-DAC PLFC-DAC p1= 25/105 p1= 75/105 0 0.5 1 1.5 0 20 40 60 80 0.4 0.5 0.6 0.7 0.8 0.9 1 P2 p1= 50/105 p1= 105/105 Figure 6. CPU time on the <15,5> random problem class. References Bacchus F. and Grove A. (1995). On the Forward Checking Algorithm, Proceedings of CP-95, 292-309. Bakker R., Dikker F., Tempelman F. and Wognum P. (1993). Diagnosing and solving overdetermined constraint satisfaction problems, Proceedings of IJCAI-93, 276281. Cabon B., Verfaille G., Martinez D. and Bourret P. (1996) Using Mean Field Methods for Boosting Backtrack Search in Constraint Satisfaction Problems, Proceedings of ECAI-96, 165-169. Dent M. and Mercer R. (1994). Minimal forward checking, Proceedings of TAI-94, 432-438. Feldman R. and Golumbic M. C. (1990). Optimization algorithms for student scheduling via constraint satisfiability, Computer Journal, vol. 33, 356-364. Fox M. (1987). Constraint-directed Search: A Case Study on Jop-Shop Scheduling. Morgan-Kauffman. Freuder E. C. and Wallace R. J. (1992). Partial constraint satisfaction, Artificial Intelligence, 58: 21-70. Larrosa J. and Meseguer P. (1995). Optimization-based Heuristics for Maximal Constraint Satisfaction, Proceedings of CP-95, 103-120. Larrosa J. and Meseguer P. (1996). Exploiting the use of DAC in MAX-CSP. Proceedings of CP-96, 308-322. Prosser P. (1994). Binary constraint satisfaction problems: some are harder than others, Proceedings of ECAI-94, 95-99. Schiex T., Regin J.C., Gaspin C., and Verfaille G. (1996). Lazy Arc Consistency, Proceedings of AAAI-96, 216-221. Wallace R. J. and Freuder E. C. (1993). Conjunctive width heuristics for maximal constraint satisfaction, Proceedings of AAAI-93, 762-778. Wallace R. J. (1994). Directed Arc Consistency Preprocessing as a Strategy for Maximal Constraint Satisfaction, ECAI94 Workshop on Constraint Processing, M. Meyer editor, 69-77. Wallace R. J. (1996). Enhancements of Branch and Bound Methods for the Maximal Constraint Satisfaction Problem, Proceedings of AAAI-96, 188-195. Zweben M. and Eskey M. (1989). Constraint Satisfaction with Delayed Evaluation, Proceedings of IJCAI-96, 875-880.