Within artificial intelligence and operations research for constraint satisfaction a hybrid algorithm solves a constraint satisfaction problem by the combination of two different methods, for example variable conditioning (backtracking, backjumping, etc.)
Hybrid algorithms exploit the good properties of different methods by applying them to problems they can efficiently solve.
This hybrid algorithm is based on running search over a set of variables and inference over the other ones.
On some kinds of problems, efficient and complete inference algorithms exist.
For example, problems whose primal or dual graphs are trees or forests can be solved in polynomial time.
Indeed, once a variable is evaluated, it can effectively removed from the graph, restricting all constraints it is involved with its value.
On the one hand, the smaller the cutset, the smaller the subproblem to be solved by search; since inference is efficient on trees, search is the part that mostly affects efficiency.
On the other hand, finding a minimal-size cutset is a hard problem.
Another alternative to reduce the running time of search is to place more burden on the inference part.
This can be exploited by doing search on a set of variables that is not a cycle cutset but leaves the problem, once removed, to be have induced width bounded by some value
-cutset of non-minimal size can be found easily for a fixed order of the variables.
In particular, such a cutset will leave a remaining graph of width bounded by
The algorithm for finding such a cutset proceed by mimicking the procedure for finding the induced graph of a problem according to the considered order of the variables (this procedure proceeds from the last node in the ordering to the first, adding an edge between every pair of unconnected parents of every node).
An alternative to using this algorithm is to let search evaluate variables, but check at each step whether the remaining graph is a forest, and run inference if this is the case.
In general, a constraint satisfaction problem can be solved by first creating a tree decomposition and then using a specialized algorithm.
A hybrid approach can be taken by using variable elimination for creating the new constraints that are propagated within nodes, and a search algorithm (such as backtracking, backjumping, local search) on each individual node.