Progressive stochastic search for solving constraint satisfaction problems

Stochastic search methods have attracted much attention of the constraint satisfaction problem (CSP) research community. Traditionally, a stochastic solver escapes from local optima or leaves plateaus by random restart or heuristic learning. In this paper, we propose the progressive stochastic search (PSS) and its variants for solving binary CSPs, in which a variable always has to choose a new value when it is designated to be repaired. Intuitively, the search can be thought to be mainly driven by a "force" to "rush through" the local minima and plateaus. Timing results show that this approach significantly outperforms LSDL(GENET) (Choi et al, 2000) in N-Queens, Latin squares, random permutation generation problems and randomly CSPs, while it fails to win LSDL(GENET) in quasigroup completion problems and increasing permutation generation problems. This prompts an interesting new research direction in the design of stochastic search schemes.