Local search for valued constraint satisfaction

Abstract

Many combinatorial optimisation problems take the form of maximising a fitness func- tion subject to some valued constraints on a collection of variables, which we call a valued constraint satisfaction problem (VCSP). We consider VCSPs where the space of assignments is endowed with a neighbourhood structure. Typically, two variable assign- ments are considered adjacent if they differ at exactly one position. We can now ask the following question: what is the complexity of greedy local search on VCSPs?

On the one hand, Kaznatcheev, Cohen and Jeavons have shown that on tree- structured Boolean VCSPs, all local search methods have a O(n^2) worst-case running time. We show that on a more restricted class, namely those VCSPs whose constraint graph is a star, the greedy local search method has a worst-case O(n) running time. In general, it is still possible for local search methods to take quadratic time to terminate however.

On the other hand, Cohen, Cooper, Kaznatcheev and Wallace have pre- sented an example of a pathwidth-7 VCSP on which greedy local search has a worst-case exponential running time. We abstract the technique they use into a general method for turning specific types of ascents – namely ones whose flips come from a priority order- ing – into steepest ascents, while limiting the increase in pathwidth for the associated VCSP. This allows us to create a VCSP of pathwidth-4 on which greedy local search has a worst-case exponential running time. Moreover, by inverting the order of the two steps taken in the approach by Cohen, Cooper, Kaznatcheev and Wallace, we obtain a binary Boolean VCSP of pathwidth 2 on which greedy local search has a worst-case exponential running time. Through this, we fully resolve the open question of the worst-case time complexity of the greedy local search method on classes of Boolean VCSPs parametrised by pathwidth.