Bram Cohen (bramcohen) wrote,
Bram Cohen

Improving Walksat

I was thinking about Walksat recently and came up with an idea.

Let us consider 3sat only and start with the question: why does walksat work so well? Consider the model where we have only a single satisfying assignment, and some number of variables are right. With walksat, no matter what properties the problem has, the chances of walksat making a mistake if it picks a variable at random to flip (as opposed to trying to be clever and pick the heuristically guessed 'optimal' one) is at most 2/3. If that value were 1/2 or greater, as is the case in 2sat, then it would almost always find a solution quickly. In practice, being off by a mere 1/6 like that is pretty good. It's surprisingly difficult to come up with a technique which manages a hard cap like this - just about any heuristics you add can lead you in the exact wrong direction if the problem is appropriately structured.

Here's the breakdown of possibilities. If the selected false clause has one variable wrong, then the expected change in number of correct values is -1/3. If it has two variables wrong, the expected change is +1/3, and if three the expected change is +1.

This expected change in number of correct variables approach leads to a few ideas. For example: instead of flipping just one variable, flip two. Then if there is one variable wrong the expected change is -2/3, if two the expected change is +2/3, and if three +2. These values are exactly double the values of only flipping one variable, so they have similar behavior but greater variance, which should, if we pretend this is a random walk, result in finding a solution faster. This technique also has the odd property that it doesn't change whether the number of variable set to true is even or odd, so it has to be run for either case. This is actually a big win - randomly searching two spaces of half size with a random walk requires on average a lot less steps than random walking a single space of double size, and it parallelizes perfectly.

Here's another idea: We have two cases, either (a) all variables in the selected clause are wrong, or (b) at least one of the variables in the selected clause is right. We'll have some tunable parameter which is the probability of dealing with the selected clause based on either assumption. If we guess (a), then we simply flip all three variables. If we guess (b), then we pick one variable which we think to be correct, and take all unsatisfied clauses which that variable appears in and flip one of the other two variables, picked at random. It's hard to fully analyze this heuristic, but it has a number of nice properties - if you pick the everything is wrong case the probability distribution is similar to that in other heuristics, and if you pick the guess one is right case then if you pick a variable which you guess is right correctly then the expected change in correct assignments is guaranteed to be nonnegative.

All of these variants, unfortunately, suffer from the same basic weakness: if all unsatisfied clauses have two variables set correctly, you're on average going to take a step backwards. This especially becomes a problem as you get close to a solution.

Oddly, the wikipedia page on walksat doesn't contain either a link to the paper on it which I coauthored or a mention of me, even though I came up with the idea (of walksat, not gsat, which walksat is a slight variant of).

  • Moving

    I've moved my blog over to See you all there!

  • Practical Cryptography Corrected

    The book 'Practical Cryptography' is perfectly good for giving an overview of basic concepts in cryptography, but its immediate practical advice to…

  • Git Can't Be Made Consistent

    This post complains about Git lacking eventual consistency. I have a little secret for you: Git can't be made to have eventual consistency.…

  • Post a new comment


    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded