A lot is known about Stochastic Local Search (sls) methods [e g. Hoos-Stutzle ’04], especially their behavior on random 3-sat

A lot is known about Stochastic Local Search (SLS) methods [e.g. Hoos-Stutzle ’04], especially their behavior on random 3-SAT

• A lot is known about Stochastic Local Search (SLS) methods [e.g. Hoos-Stutzle ’04], especially their behavior on random 3-SAT

• Along with systematic search, the main SAT solution paradigm
• Walksat one of the first widely successful local search solver
• Biased random walk
• Combines greedy moves (downhill) with stochastic moves (possibly uphill) controlled by a “noise” parameter [0% .. 100%]

• Yet, new surprising findings are still being discovered

• Part of this work motivated by the following observation:

Our work looks at Walksat again, on large, random, 3-SAT formulas, and seeks answers to two questions:

• Our work looks at Walksat again, on large, random, 3-SAT formulas, and seeks answers to two questions:

• Can we further characterize the “optimal noise” and the linear scaling behavior of Walksat?
• Key parameter: the clause-to-variable ratio, α
• How do runtime distributions of Walksat behave at sub-optimal noise?
• Are they concentrated around the mean or do they have “heavy tails” similar to complete search methods?
• Heavy tails  very long runs more likely than we might expect
• Heavy tails not reported in local search so far

• Note: Walksat still faster than current adaptive, dynamic noise solvers on these formulas; studying behavior at optimal static noise of much interest

Walksat on large, random, 3-SAT formulas:

• Walksat on large, random, 3-SAT formulas:

• Further characterization the “optimal noise” and linear scaling:
• A detailed analysis, showing a piece-wise linear fit for optimal noise as a function of α, with transitions at interesting points (extending the previous observation that ~57% is optimal for α=4.2)
• Simple inverse polynomial dependence of runtime on α
• Runtime distributions of Walksat behave at sub-optimal noise
• Exponential decay in the high noise regime
• Heavy tails in the low noise regime First quantitative observation of heavy tails in local search [earlier insights: Hoos-Stutzle 2000]
• Preliminary Markov Chain model

Question:

• Question:

• How does the optimal noise setting vary with α and N?

• Experiment:

• For α in [1.5...4.2], generate random 3-SAT formulas with N in [100K..400K]
• For each, find the noise setting where Walksat is the fastest (binary search)
• Average these optimal noise settings and plot against α

Experiment:

• Experiment:

• For α in [1.5...4.2], generate random 3-SAT formulas with N in [100K..400K]
• Measure Walksat's runtime with optimal noise (#flips till solution found)
• Plot #flips/N against α (one point per run, no averaging)

• Results: Inverse polynomial fit of #flips/N as a function of α

• Suggesting linear scaling for α < 4.235

Standard distributions:

• Standard distributions:

• Exponential or faster decay e.g., Normal distribution

• Heavy-tailed distributions:

• Power law decay e.g. Pareto-Levy distribution

• Heavy-tailed distributions:

• Power law decay e.g. Pareto-Levy distribution
• Signature: tail of the distribution is a line in log-log plot
• Observed in systematic search solvers
• Mechanism well-understood in terms of “bad” variable assignments that are hard to recover from [Gomes, Kautz and Selman ‘99, ’00]
• Motivated key techniques such as search restarts, algorithm portfolios
• Not previously observed in studies on local search methods

• Experiment:

• Generate a random 3-SAT formula with N=100K at α=4.2
• Large formulas, free of small size effects
• Very hard to solve
• Still less constrained than formulas at the phase transition (α4.26)
• Run 100K (!) runs of Walksat with noise settings around the optimal
• Plot the runtime distribution: probability of failure to find a solution as a function of #flips

[Setting: Large, random, 3-SAT formula with α=4.2]

• [Setting: Large, random, 3-SAT formula with α=4.2]

• Summary of Results:

• There is a qualitative difference between noise higher that optimal (>56.7%) and lower that optimal (<56.7%)
• High noise regime: tail of P[failure] has an exponential distribution
• Low noise regime : tail of P[failure] has a power-law distribution
• Intuition captured by a (preliminary) Markov Chain model
• High noise means “guessing the solution”
• Low noise (too greedy) leads the search into “local traps”
• Optimal noise is where the two effects balance