ARTIFICIAL INTELLIGENCE 273 Enhancement Schemes for Constraint Processing: Backjumping, Learning, and Cutset Decomposition* Rina Dechter** Cognitive System Laboratory, Computer Science Department, Universtty of Californta, Los Angeles, CA 90024, USA ABSTRACT Researchers m the areas of constramt sattsfactton problems, logtc programmmg, and truth mamte- nance systems have suggested vartous schemes for enhancmg the performance of the backtracking algorithm Thts paper defines and compares the performance of three such schemes "backlumpmg," "learmng," and "cycle-cutset " The backlumpmg and the cycle-cutset methods work best when the constramt graph is sparse, whde the learnmg scheme mostly benefits problem mstances wtth dense constramt graphs An integrated strategy ts described whwh utdtzes the dzstmct advantages of each scheme Expertments show that, m hard problems, the average tmprovement reahzed by the mtegrated scheme ts 20-25% higher than any of the mdtvtdual schemes I. Introduction Backtracking search is a prominent processing technique in Artificial Intellig- ence, in particular due to its use in PROLOG [2, 4, 20, 35], truth maintenance systems (TMSs) [9, 21, 26, 29, 32], and constraint satisfaction problems (CSPs) [5, 12-14, 17, 24, 25, 28]. In recent years there has been great emphasis in all of these areas on developing methods for improvmg backtrackmg efficiency. The terms "intelligent backtracking," "selective backtracking," and "depen- dency-directed backtracking" denote such ~mprovements. The main trust of these efforts is to enhance the chronological nature of the textbook backtrack- lng algorithm with mechamsms that faclhtate more informed decisions at various stages of the search. The standard backtracking search algorithm attempts to assign values to a set *This work is supported m part by the National Science Foundation, Grant #IRI-8501234 A substantml part of th~s work was performed whde the author was at the Art~ficlal-Intelhgence Center at Hughes, Calabassass ** Current address Computer Science Department, Techmon--Israel Institute of Technology, Techmon City, Halfa 32000, Israel Arttfictal lntelhgence 41 (1989/90) 273-312 0004-3702/90/$3 50 © 1990, Elsevier Science Pubhshers B V (North-Holland)274 R DECHTER of variables so that all the given constraints among the variables are satisfied. The algorithm typically considers the variables in some order and, starting with the frst, assigns a value, taken from a set of possible values, to each successive variable in turn as long as the assigned value is consistent with the values assigned to the preceding variables. When, in the process, a variable is encountered such that none of its possible values is consistent with previous assignments (a situation referred to as a dead-end), backtracking takes place. That is, the value assigned to the immediately preceding variable is replaced, and the search continues in a systematic way until either a solution (1.e, assignment ot values to all variables) is found or until it may be concluded that no such solution exists Improving backtracking efficiency amounts to reducing the size of the search space expanded by the algorithm. The size of the search space is greatly dependent on the way the constraints are represented. Generally speaking, the algorithm will benefit from representations which are more exphctt, that is, when constraints are spelled out exphcltly, even if they are implied by other constraints. The size of the search space is also heavily influenced by user- specific choices such as the variable ordering and, when one solution suffices, the order in which values are assigned to each variable. In trying to use these factors to improve the performance of backtracking algorithms, researchers have developed procedures of two types: those that are employed m advance of performing the search, and those that are used dynamically during search Techniques designed to be applied in advance Include a variety of consistency enforcing algorithms [18, 24]. These algorithms transform a given constraint network into an equivalent, but more exphclt network by using the given constraints to deduce new constraints which are then added to the network There are also several heuristics that have been proposed for the purpose of deciding the ordering of the variables prior to performing backtracking search [7, 12]. Strategies for dynamically improving the pruning power of backtracking can be conveniently classified as lookahead schemes and lookback schemes. Lookahead schemes are invoked whenever the algorithm is preparing to assign a value to the next variable. Some of the functions that such schemes perform are' (1) Calculate and record the way in which the current instantlations restrict future variables. This process has been referred to as constraint propagation. Examples include Waltz's algorithm [36] and forward checking [14]. (2) Decide which variable to instantiate next (when the order is not pre- determined). Generally, it is advantageous to first lnstantlate variables which maximally constrain the rest of the search space. Therefore, the variable par- tlclpatlng in the highest number of constraints is usually selected [12, 28, 33, 37]. (3) Decide which value to assign to the next variable (when there is more than one candidate) Generally, for finding one solution, an attempt is made toENHANCEMENT SCHEMES FOR CONSTRAINT PROCESSING 275 assign a value that maximizes the number of options available for future assignments [5, 14]. Lookback schemes are invoked when the algorithm encounters a dead-end and prepares for the backtracking step. These schemes perform two functions: (1) Decide how far to backtrack. By analyzing the reasons for the dead-end it is often possible to go back directly to the source of failure instead of to the previous variable in the ordering. This idea is often referred to as dependency- dtrected backtracking [32] or backjumping [13]. (2) Recordmg the