Conflict-Directed Backjumping (CBJ)

The core innovation of CBJ is its non-chronological backtracking. When a dead-end is reached, the algorithm analyzes the conflict set—the set of past variable assignments that collectively caused the failure. It then jumps back to the most recent variable in this conflict set, bypassing any intermediate variables whose assignments were irrelevant to the failure. This directly targets the source of the inconsistency, pruning large, irrelevant portions of the search tree that a naive backtracker would explore.

CBJ dynamically maintains a conflict set for each variable. When a variable X_i is assigned a value, its conflict set is initialized as empty. If a subsequent variable X_j fails to find a value compatible with X_i's assignment, X_i is added to X_j's conflict set. This bookkeeping is crucial. Upon backtracking, the algorithm computes a new conflict set for the target variable by merging the conflict sets of all failed downstream variables, minus itself. This merged set precisely identifies the relevant past decisions that must be changed.

The backtracking jump is determined by finding the deepest variable in the union of conflict sets from the point of failure. For example, if variable X_5 fails and its conflict set is {X_2, X_4}, the algorithm will jump back to X_4 (the most recent culprit), not to X_3. It then removes the failed value from X_4's domain and updates X_4's conflict set to {X_2}. This mechanism ensures search effort is focused only on reassigning variables that actually participated in the conflict.

CBJ is most powerful when combined with a lookahead technique like forward checking. Forward checking propagates the implications of an assignment, pruning incompatible values from the domains of unassigned variables. When forward checking results in a domain wipeout (an unassigned variable's domain becomes empty), it immediately identifies a conflict. CBJ then uses this early failure signal to trigger its backjumping analysis, preventing the search from proceeding down a provably futile branch.

Chronological backtracking (used in naive DFS) always backtracks to the immediately preceding variable, a method often called backtracking search. This is highly inefficient for constraint satisfaction problems (CSPs) with localized conflicts. CBJ provides a dramatic improvement:

• Chronological: Backtracks one step at a time, re-exploring many irrelevant value combinations.
• CBJ: Identifies the true source of failure, often jumping back multiple levels, eliminating exponential amounts of redundant search. This makes CBJ essential for solving large, hard CSPs like scheduling or configuration.

CBJ is a direct precursor and conceptual sibling to Conflict-Driven Clause Learning (CDCL) used in modern Boolean satisfiability (SAT) solvers. Both paradigms share the core idea:

• Analyze failure to derive a precise reason (a conflict set in CBJ, a learned clause in CDCL).
• Jump back non-chronologically to the decision that caused the conflict.
• Record the reason to prevent the same conflict in the future. While CDCL operates on Boolean clauses and uses more sophisticated implication graphs, the fundamental 'conflict-directed backjumping' insight is identical, highlighting CBJ's foundational role in advanced combinatorial search.

A family of inference techniques used to prune the search space before and during search. By using the constraints to eliminate values from variable domains that cannot participate in any solution, it reduces the branching factor for algorithms like CBJ. Key methods include:

• Node consistency: Ensures each value in a domain satisfies the variable's unary constraints.
• Arc consistency: For binary constraints, ensures every value in a variable's domain has a compatible value in the domain of the other variable.
• Path consistency: Extends this reasoning to triplets of variables.

A powerful hybrid search algorithm that combines backtracking with full arc consistency enforcement. At each node in the search tree, MAC runs an algorithm like AC-3 to prune domains. If a variable's domain becomes empty, it triggers a backtrack. CBJ is often integrated with MAC to create MAC-CBJ, a highly efficient algorithm where the conflict set used for backjumping is derived from the domain wipe-outs detected during constraint propagation.

The dominant architecture for modern Boolean Satisfiability (SAT) solvers. Like CBJ, it analyzes failures to learn and backtrack intelligently. Key parallels include:

• Non-chronological backtracking: Jumps back more than one level, similar to CBJ's backjump.
• Conflict analysis: Identifies the root cause of a contradiction to derive a new clause (constraint).
• Clause learning: Adds this new clause to the problem to prevent the same dead-end. CDCL operates on Boolean formulas, while CBJ operates on general CSPs, but the core 'conflict-directed' insight is shared.

The naive, depth-first baseline algorithm that CBJ improves upon. Standard backtracking:

1. Assigns a value to a variable.
2. Moves forward to the next variable.
3. Upon a dead-end (no legal value), it backtracks chronologically to the most recently assigned variable. The critical weakness is that it may backtrack through variables that are unrelated to the failure. CBJ's innovation is to analyze the conflict to jump back directly to a culprit variable, making search more efficient.

A critical search heuristic often used alongside CBJ. Instead of fixing the order to assign variables at the start, DVO selects the next variable dynamically during search. The most common heuristic is Minimum Remaining Values (MRV), which chooses the variable with the smallest domain. This 'fail-first' principle creates dead-ends earlier, allowing CBJ to prune larger, fruitless subtrees sooner. DVO and CBJ are complementary techniques for intelligent search.

The extension of a CSP where solutions must not only satisfy constraints but also optimize an objective function (e.g., minimize cost, maximize utility). Algorithms for COPs, like Branch and Bound, must search through feasible solutions. CBJ can be adapted for use in optimization search to efficiently prune subspaces that are provably suboptimal or infeasible, though the conflict analysis must also consider bounds on the objective.