Unweighted Stochastic Local Search can be Effective for Random CSP Benchmarks

We present ULSA, a novel stochastic local search algorithm for random binary constraint satisfaction problems (CSP). ULSA is many times faster than the prior state of the art on a widely-studied suite of random CSP benchmarks. Unlike the best previous methods for these benchmarks, ULSA is a simple unweighted method that does not require dynamic adaptation of weights or penalties. ULSA obtains new record best solutions satisfying 99 of 100 variables in the challenging frb100-40 benchmark instance. 1 Random Binary CSPs Randomly generated instances of constraint satisfaction problems (CSP) have provided widely-used benchmarks in the development of solvers for CSP, Boolean satisfiability (SAT), and maximum independent set (MIS). While some interesting instances of CSP and SAT eventually turn out to be reasonably easy for appropriate methods (Minton, Johnston, Philips, & Laird, 1990; Williams, Gomes, & Selman, 2003), reliably hard instances of random CSP can be obtained from the “phase transition ” boundary between satisfiable and unsatisfiable regions of parameterized distributions of instances (Prosser, 1996). For appropriate distributions, most of these phase transition instance