A hybrid search architecture applied to hard random 3-SAT and low-autocorrelation binary sequences

The hybridisation of systematic and stochastic search is an active research area with potential benefits for real-world combinatorial problems. This paper shows that randomisingthe backtracking component of a systematic backtracker can improve its scalability to equal that of stochastic local search. The hybrid may be viewed as stochastic local search in a constrained space, cleanly combininglo cal search with constraint programming techniques. The approach is applied to two very different problems. Firstly a hybrid of local search and constraint propagation is applied to hard random 3-SAT problems, and is the first constructive search algorithm to solve very large instances. Secondly a hybrid of local search and branch-and-bound is applied to lowautocorrelation binary sequences (a notoriously difficult communications engineering problem), and is the first stochastic search algorithm to find optimal solutions. These results show that the approach is a promising one for both constraint satisfaction and optimisation problems.