Striking examples of success of local search algorithms

Question

In N queens problem https://en.wikipedia.org/wiki/Eight_queens_puzzle, trying to find solution by backtracking encounters difficulties quite fast (even for SWI-Prolog, http://swish.swi-prolog.org/example/clpfd_queens.pl, which solves N=100 in 0.2 sec, entering N=150 in the link above did not reach a solution in a reasonable amount of time ("time limit exceeded"), and as for ECLiPSe (another Prolog with constraint poropagation) it chokes much, much earlier..).

On the other hand, local search works incredibly well on this problem (https://stackoverflow.com/questions/1863531/n-queens-probiem-how-far-can-we-go, answer by the user chesslover), as the solutions seem to be reachable easily enough by hill climbing (or rather, in this case, hill descending with occasional short range climbing), starting from a random position in the space of possible configurations (each column is occupied by exactly one queen).

Which other well known problems appear to have similar properties (say, a part from examples given in https://en.wikipedia.org/wiki/Local_search_(optimization))?

Answer 1

The following paper

• S. D. Prestwich, "Local search and backtracking vs non-systematic backtracking," in AAAI 2001 Fall Symp. Uncertainty Computation, 2001. Alternative link to a PDF.

has a thorough comparison of local search vs. backtracking-like algorithm. In the introduction, it even features a question:

"What is the essential difference between local search and backtracking, that sometimes enables local search causes to scale far better than backtracking"

While describing his variation of a hybrid local search + backtracking algorithm, Prestwich tests it on

• classic $N$ queens problem
• graph coloring with "real-world applications to timetabling, scheduling, frequency assignment, computer register allocation, printed circuit board testing, and pattern matching"
• satisfiability (SAT)

All of the above (with possible specialization) can serve as examples for your question.

The other reference that is directly related to a comparison of local search algorithm to backtracking-like is:

• E. C. Freuder et al.,"Systematic versus stochastic constraint satisfaction," in _Proc. 14th Int. Joint Conf. Artificial Intelligence, Montreal, QC, Canada, pp. 2027–2032, 1995.

which will also talk about the possible reasons for local search to perform better than backtracking.

In general, the possible reasons can be summarized as (Prestwich, 2001):

• randomness
• incompleteness
• scalability
• different search space
• ability to follow gradients
• backtracking's commitment to early variable assignments

The last reference that came to my mind is a nice PhD Thesis

• J. Ward, "Oblivious and non-oblivious local search for combinatorial optimization," PhD. Thesis, Univ. Toronto, Dept. Comput. Sci., 2012.

that will feature a couple of other (depends on categorization) applications for local search, where backtracking suffers.