Live briefing
Everything about Backjumping
In backtracking algorithms, technique that reduces search space
In constraint programming and SAT solving, backjumping is an enhancement for backtracking algorithms which reduces the search space. 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 is used, but the same considerations apply to a dynamic order of evaluation. Wikipedia →
🧭 Start here: a 6-step reading path
- Read the overview: BackjumpingA 5-minute orientation
- Skim a recent paper: Implementing Backjumping by Means of Exception HandlingInfluential work since 2022
- Read the landmark paper: Enhancement schemes for constraint processing: Backjumping, learning, and cutset decompositionCited 287 times
- Go sideways: Constraint learningA closely related topic
- Go sideways: BackmarkingA closely related topic
📖 Definitions
Noun A form of backtracking that may move more than one level at a time, used to improve the efficiency of certain algorithms.
🗂️ The subject at a glance
🏆 Landmark papers (most cited)
Enhancement schemes for constraint processing: Backjumping, learning, and cutset decomposition
Conflict-Directed Backjumping Revisited
Backjumping for Quantified Boolean Logic satisfiability
Enhancing DLV instantiator by backjumping techniques
Abstract answer set solvers with backjumping and learning
Enhanced Multiple-Point Statistical Simulation with Backtracking, Forward Checking and Conflict-Directed Backjumping
Efficient Generation of Stimuli for Functional Verification by Backjumping Across Extended FSMs
Constraint-based BMC: a backjumping strategy
🆕 Influential since 2022
📚 Books worth reading
Open Library didn't respond; try again in a moment.
🔗 Related topics
- Constraint learning In constraint satisfaction backtracking algorithms, constraint learning is a technique for improving efficiency. It works by recording new constraints…
- Backmarking In constraint satisfaction, backmarking is a variant of the backtracking algorithm. Backmarking works like backtracking by iteratively evaluating variables…
- Constrained optimization In mathematical optimization, constrained optimization (in some contexts called constraint optimization) is the process of optimizing an objective function…
- Local consistency In constraint satisfaction, local consistency conditions are properties of constraint satisfaction problems related to the consistency of subsets of variables…
- Hybrid algorithm (constraint satisfaction) Within artificial intelligence and operations research for constraint satisfaction a hybrid algorithm solves a constraint satisfaction problem by the combinatio…
- Backtracking Backtracking is a class of algorithms for finding solutions to some computational problems, notably constraint satisfaction or enumeration problems, that…
- Interchangeability algorithm In computer science, an interchangeability algorithm is a technique used to more efficiently solve constraint satisfaction problems (CSP). A CSP is a mathematic…
- Local search (constraint satisfaction) In constraint satisfaction, local search is an incomplete method for finding a solution to a problem. It is based on iteratively improving an assignment…