Hybrid algorithm (constraint satisfaction)

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.

Another alternative to reduce the running time of search is to place more burden on the inference part. In particular, inference can be relatively efficient even if the problem graph is not a forest but a graph of small induced width. 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 b . Such set of variables is called a b -cutset of the problem.

The induced width of a graph after a set of variables is removed is called adjusted induced width. Therefore, the induced width adjusted relative to a b cutset is always b . Finding a minimal-size b -cutset is in general hard. However, a b -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 b according to that particular order of the variables.

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). Whenever this procedure would find or make a node having more than b parents, the node is removed from the graph and added to the cutset. By definition, the resulting graph contains no node of width greater than b , and the set of removed nodes is therefore a b -cutset.

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 other words, instead of finding a set of variables at the beginning and use only them during search, the algorithm starts as a regular search; at each step, if the assigned variables form a b cutset of the problem, inference is run to check satisfiability. This is feasible because checking whether a given set of nodes is a b cutset for a fixed b 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.