Backjumping

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In backtracking algorithms, backjumping is a technique that reduces search space, therefore increasing efficiency. While backtracking always goes up one level in the search tree when all values for a variable have been tested, backjumping may go up more levels. In this article, a fixed order of evaluation of variables x_1,\ldots,x_n is used, but the same considerations apply to a dynamic order of evaluation.

Definition[edit]

Whenever backtracking has tried all values for a variable without finding any solution, it reconsiders the last of the previously assigned variables, changing its value or further backtracking if no other values are to be tried. If x_1=a_1,\ldots,x_k=a_k is the current partial assignment and all values for x_{k+1} have been tried without finding a solution, backtracking concludes that no solution extending x_1=a_1,\ldots,x_k=a_k exists. It then "goes up" to x_k, changing its value if possible, backtracking again otherwise.

The partial assignment is not always necessary in full to prove that no value of x_{k+1} lead to a solution. In particular, a prefix of the partial assignment may have the same property, that is, there exists an index j<k such that x_1,\ldots,x_j=a_1,\ldots,a_j cannot be extended to form a solution with whatever value for x_{k+1}. If the algorithm can prove this fact, it can directly consider a different value for x_j instead of reconsidering x_k as it would normally do.

Backjump-variables-1.svg Backjump-variables-2.svg Backjump-variables-3.svg
An example in which the current assignment to x_1x_2x_3x_4 has been unsuccessfully tried with every possible value of x_5. Backtracking goes back to x_4, trying to assign it a new value. Instead of backtracking, the algorithm makes some further elaboration, proving that the evaluations x_1x_2x_5=211, x_1x_5=22, and x_1x_2x_5=213 are not part of any solution. As a result, the current evaluation of x_1x_2 is not part of any solution, and the algorithm can directly backjump to x_2, trying a new value for it.

The efficiency of a backjumping algorithm depends on how high it is able to backjump. Ideally, the algorithm could jump from x_{k+1} to whichever variable x_j is such that the current assignment to x_1,\ldots,x_j cannot be extended to form a solution with any value of x_{k+1}. If this is the case, j is called a safe jump.

Establishing whether a jump is safe is not always feasible, as safe jumps are defined in terms of the set of solutions, which is what the algorithm is trying to find. In practice, backjumping algorithms use the lowest index they can efficiently prove to be a safe jump. Different algorithms use different methods for determining whether a jump is safe. These methods have different cost, but a higher cost of finding a higher safe jump may be traded off a reduced amount of search due to skipping parts of the search tree.

Backjumping at leaf nodes[edit]

The simplest condition in which backjumping is possible is when all values of a variable have been proved inconsistent without further branching. In constraint satisfaction, a partial evaluation is consistent if and only if it satisfies all constraints involving the assigned variables, and inconsistent otherwise. It might be the case that a consistent partial solution cannot be extended to a consistent complete solution because some of the unassigned variables may not be assigned without violating other constraints.

The condition in which all values of a given variable x_{k+1} are inconsistent with the current partial solution x_1,\ldots,x_k=a_1,\ldots,a_k is called a leaf dead end. This happens exactly when the variable x_{k+1} is a leaf of the search tree (which correspond to nodes having only leaves as children in the figures of this article.)

The backjumping algorithm by Gaschnig does a backjump only in leaf dead ends. In other words, it works differently from backtracking only when every possible value of x_{k+1} has been tested and resulted inconsistent without the need of branching over another variable.

A safe jump can be found by simply evaluating, for every value a_{k+1}, the shortest prefix of x_1,\ldots,x_k=a_1,\ldots,a_k inconsistent with x_{k+1}=a_{k+1}. In other words, if a_{k+1} is a possible value for x_{k+1}, the algorithm checks the consistency of the following evaluations:

x_1=a_1 ... x_{k-1}=a_{k-1} x_k=a_k x_{k+1}=a_{k+1}
x_1=a_1 ... x_{k-1}=a_{k-1} x_{k+1}=a_{k+1}
...
x_1=a_1 x_{k+1}=a_{k+1}

The smallest index (lowest the listing) for which evaluations are inconsistent would be a safe jump if x_{k+1}=a_{k+1} were the only possible value for x_{k+1}. Since every variable can usually take more than one value, the maximal index that comes out from the check for each value is a safe jump, and is the point where Gaschnig's algorithm jumps.

In practice, the algorithm can check the evaluations above at the same time it is checking the consistency of x_{k+1}=a_{k+1}.

Backjumping at internal nodes[edit]

The previous algorithm only backjumps when the values of a variable can be shown inconsistent with the current partial solution without further branching. In other words, it allows for a backjump only at leaf nodes in the search tree.

An internal node of the search tree represents an assignment of a variable that is consistent with the previous ones. If no solution extends this assignment, the previous algorithm always backtracks: no backjump is done in this case.

Backjumping at internal nodes cannot be done as for leaf nodes. Indeed, if some evaluations of x_{k+1} required branching, it is because they are consistent with the current assignment. As a result, searching for a prefix that is inconsistent with these values of the last variable does not succeed.

In such cases, what proved an evaluation x_{k+1}=a_{k+1} not to be part of a solution with the current partial evaluation x_1,\ldots,x_k is the recursive search. In particular, the algorithm "knows" that no solution exists from this point on because it comes back to this node instead of stopping after having found a solution.

This return is due to a number of dead ends, points where the algorithm has proved a partial solution inconsistent. In order to further backjump, the algorithm has to take into account that the impossibility of finding solutions is due to these dead ends. In particular, the safe jumps are indexes of prefixes that still make these dead ends to be inconsistent partial solutions.

Dead-ends-1.svg Dead-ends-1a.svg Dead-ends-2.svg Dead-ends-3.svg
In this example, the algorithm come back to x_{k+1}, after trying all its possible values, because of the three crossed points of inconsistency. The second point remains inconsistent even if the values of x_{k+1} and x_k are removed from its partial evaluation (note that the values of a variable are in its children) The other inconsistent evaluations remains so even without x_{k-2}, x_{k-1}, and x_k The algorithm can backjump to x_{k-2} since this is the lowest variables that maintains all inconsistencies. A new value for x_{k-2} will be tried.

In other words, when all values of x_{k+1} have been tried, the algorithm can backjump to a variable x_i provided that the current truth evaluation of x_1,\ldots,x_i is inconsistent with all the truth evaluations of x_{k+1},x_{k+2},... in the leaf nodes that are descendants of the node x_{k+1}.

Simplifications[edit]

While looking for a possible backjump for x_{k+1} or one its ancestors, all nodes in the shaded area can be ignored.

Due to the potentially high number of nodes that are in the subtree of x_{k+1}, the information that is necessary to safely backjump from x_{k+1} is collected during the visit of its subtree. Finding a safe jump can be simplified by two considerations. The first is that the algorithm needs a safe jump, but still works with a jump that is not the highest possible safe jump.

The second simplification is that nodes in the subtree of x_l that have been skipped by a backjump can be ignored while looking for a backjump for x_l. More precisely, all nodes skipped by a backjump from node x_m up to node x_l are irrelevant to the subtree rooted at x_m, and also irrelevant are their other subtrees.

Indeed, if an algorithm went down from node x_l to x_m via a path but backjumps in its way back, then it could have gone directly from x_l to x_m instead. Indeed, the backjump indicates that the nodes between x_l and x_m are irrelevant to the subtree rooted at x_m. In other words, a backjump indicates that the visit of a region of the search tree had been a mistake. This part of the search tree can therefore be ignored when considering a possible backjump from x_l or from one of its ancestors.

Variables whose values are sufficient to prove unsatisfiability in the subtree rooted at a node are collected in the node and sent (after removing the variable of the node) to the node above when retracting.

This fact can be exploited by collecting, in each node, a set of previously assigned variables whose evaluation suffices to prove that no solution exists in the subtree rooted at the node. This set is built during the execution of the algorithm. When retracting from a node, this set is removed the variable of the node and collected in the set of the destination of backtracking or backjumping. Since nodes that are skipped from backjumping are never retracted from, their sets are automatically ignored.

Graph-based backjumping[edit]

The rationale of graph-based backjumping is that a sg that no solution can be found by visiting the subtree rooted at x_{k+1}. As a result, the algorithm can backjump to the highest index in this set.


procedure GRAPH-BASED-BACKJ UMPING Input: A constraint network ~ = (X, D, C). Output: Either a solution, or a decision that the network is inconsistent. compute anc(xi) for each xi (see Definition 6.7 in text) i <--- 1 Df +-- Di li .-- anc(xi) while1 <i<n m _ _ instantiate xi ~-- SELECT-VALUE if xi is null iprev +-- i i +--latest index in li (backjump) li 4-- /i U/iprev- {Xi} else i,--i+1 Df +-- Di li *-- anc(xi) end while if i = 0 return "inconsistent" else return instantiated values of {Xl ..... Xn} end procedure (initialize variable counter) (copy domain) (copy of anc() that can change) (no value was returned) procedure SELECT-VALUE (same as BACKTRACKING'S) while D/is not empty select an arbitrary element a e Dr, and remove a from D/ if CONSISTENT(ai_ 1, Xi = <3) return a end while return null (no consistent value) end procedure

Conflict-based backjumping (aka conflict-directed backjumping (cbj))[edit]

A still more refined backjumping algorithm, sometimes able to achieve larger backjumps, is based on checking not only the common presence of two variables in the same constraint but also on whether the constraint actually caused inconsistency. In particular, this algorithm collects one of the violated constraints in every leaf. At every node, the highest index of a variable that is in one of the constraints collected at the leaves is a safe jump.

While the violated constraint chosen in each leaf does not affect the safeness of the resulting jump, choosing constraints of highest possible indices increases the highness of the jump. For this reason, conflict-based backjumping orders constraints in such a way constraints over lower indices variables are preferred over constraints on higher index variables.

Formally, a constraint C is preferred over another one D if the highest index of a variable in C but not in D is lower than the highest index of a variable in D but not in C. In other words, excluding common variables, the constraint that has the all lower indices is preferred.

In a leaf node, the algorithm chooses the lowest index i such that x_1,\ldots,x_i is inconsistent with the last variable evaluated in the leaf. Among the constraints that are violated in this evaluation, it chooses the most preferred one, and collects all its indices less than k+1. This way, when the algorithm comes back to the variable x_{k+1}, the lowest collected index identifies a safe jump.

In practice, this algorithm is simplified by collecting all indices in a single set, instead of creating a set for every value of k. In particular, the algorithm collects, in each node, all sets coming from its descendants that have not been skipped by backjumping. When retracting from this node, this set is removed the variable of the node and collected into the destination of backtracking or backjumping.

Conflict-directed backjumping was proposed for Constraint Satisfaction Problems by Patrick Prosser in his seminal 1993 paper.

See also[edit]

References[edit]