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.) and constraint inference (arc consistency, variable elimination, etc.)

Hybrid algorithms exploit the good properties of different methods by applying them to problems they can efficiently solve. For example, search is efficient when the problem has many solutions, while inference is efficient in proving unsatisfiability of overconstrained problems.

Cycle cutset inference/search algorithm

This 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 dual graphs are trees or forests can be solved in polynomial time. This affect the choice of the variables evaluated by search. Indeed, once a variable is evaluated, it can effectively removed from the graph, restricting all constraints it is involved with its value. Alternatively, an evaluated variable can be replaced by a number of distinct variables, one for each constraint, all having a single-value domain.

This mixed algorithm is efficient if the search variables are chosen so that duplicating or deleting them turns the problem into one that can be efficiently solved by inference. In particular, if these variables form a cycle cutset of the graph of the problem, inference is efficient because it has to solve a problem whose graph is a tree or, more generally, a forest. Such an algorithm is as follows:

find a cycle cutset of the graph of the problem
run search on the variables of the cutset
  when a consistent partial assignment to all variables are found,
    replace each variable of the cutset with a new variable for each constraint;
    set the domains of these new variables to the value of the old variable in the partial assignment
    solve the problem using inference

The efficiency of this algorithm depends on two contrasting factors. 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. As a result, a small cycle cutset may be used instead of a minimal one.

.-cutset of the problem.

The induced width of a graph after a set of variables is removed is called adjusted induced width according to that particular order of the variables.

-cutset.

cutset of the problem, inference is run to check satisfiability. This is feasible because checking whether a given cutset for a fixed is a polynomial problem.

Tree decomposition hybrid algorithm

Another hybrid search/inference algorithm works on the tree decomposition. In general, a constraint satisfaction problem can be solved by first creating a tree decomposition and then using a specialized algorithm.

One such algorithm is based on first propagating constraints among nodes, and then solving the subproblem in each node. This propagation consists in creating new constraints that represent the effects of the constraints in a node over a joined node. More precisely, if two nodes are joined, they share variables. The allowed evaluations of these variables according to the constraints of the first node tell how the first node affects the variables of the second node. The algorithm works by creating the constraint satisfied by these evaluations and incorporating this new constraint in the second node.

When all constraints have been propagated from the leaves to the root and back to the root, all nodes contain all constraints that are relevant to them. The problem can therefore be solved in each node.

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.

References