Very large-scale neighborhood search

In mathematical optimization, neighborhood search is a technique that tries to find good or near-optimal solutions to a combinatorial optimisation problem by repeatedly transforming a current solution into a different solution in the neighborhood of the current solution. The neighborhood of a solution is a set of similar solutions obtained by relatively simple modifications to the original solution. For a very large-scale neighborhood search, the neighborhood is large and possibly exponentially sized.

The resulting algorithms can outperform algorithms using small neighborhoods because the local improvements are larger. If neighborhood searched is limited to just one or a very small number of changes from the current solution, then it can be difficult to escape from local minima, even with additional meta-heuristic techniques such as Simulated Annealing or Tabu search. In large neighborhood search techniques, the possible changes from one solution to its neighbor may allow tens or hundreds of values to change, and this means that the size of the neighborhood may itself be sufficient to allow the search process to avoid or escape local minima, though additional meta-heuristic techniques can still improve performance.

References

• Ahuja, Ravindra K.; Orlin, James B.; Sharma, Dushyant (2000), "Very large-scale neighborhood search" (PDF), International Transactions in Operational Research, 7 (4–5): 301–317, doi:10.1111/j.1475-3995.2000.tb00201.x.