Large Neighborhood Search
Timo Berthold, Andrea Lodi, Domenico Salvagnin · Cambridge University Press eBooks · 2025
This chapter concerns the vast family of large neighborhood search primal heuristics. These are local search heuristics that generally assume the knowledge of one or more feasible MIP solutions and explore "large" neighborhoods in the attempt to improve the incumbent, i.e., the best feasible solution computed so far by the MIP algorithm. A neighborhood is large if, in general, it cannot be explored by complete enumeration, so the various techniques developed for defining those neighborhoods and exploring them are discussed.