hybrid algorithm is based on running search over a set of variables and inference over the other ones. In particular, backtracking or some other form of search is run over a number of variables; whenever a consistent partial assignment over these variables is found, inference is run over the remaining variables to check whether this partial assignment can be extended to form a solution.

On some kinds of problems, efficient and complete inference algorithms exist. For example, problems whose primal or