Local Search (constraint Satisfaction) - Local Search On A Cycle Cutset

Local Search On A Cycle Cutset

Local search usually works on all variables, improving a complete assignment to them. However, local search can also be run on a subset of variables, using some other mechanism for the other variables. A proposed algorithm works on a cycle cutset, which is a set of variables that, if removed from the problem, makes it acyclic.

For any assignment of the variables of the cutset, the remaining problem has a forest as primal graph. As a result, it can be solved efficiently. In order to guide local search, an algorithm detecting the minimal number of constraints that can be violated is used in place of a satisfiability algorithm on the for forest part of the problem.

This minimal number is found by determining the cost of each variable assignment. This cost is the minimal number of constraints violated by an assignment of the variables in the subtree rooted at the variable, when the variable takes the given value. This cost can be calculated as follows. If denotes the cost of the assignment and are the children of, the following formula holds. In this formula, is the 0 or 1 depending on whether the assignment violates the constraint between and .

The cost for variables in the cutset is zero, and these variables are assumed to be allowed to take only their given value. With these assumptions, the above formula allows computing the cost of all variable evaluations by iteratively proceeding bottom-up from the leaves to the root(s) of the forest.

The cost of variable evaluations can be used by local search for computing the cost of a solution. The cost of values of the roots of the forest is indeed the minimal number of violated constraints in the forest for these given values. These costs can therefore used to evaluate the cost of the assignment to the cutset variables and to estimate the cost of similar assignments on the cutset variables.