Large Neighborhood Search (LNS)
Large Neighborhood Search (LNS) is a heuristic optimization method designed to improve solutions to complex combinatorial and Mixed-Integer problems. It extends local search by exploring much larger portions of the solution space at each iteration. Instead of applying small modifications to a solution, LNS partially destroys a solution and then rebuilds it by solving a subproblem. This strategy allows the algorithm to escape local optima and explore new regions of the search space.
LNS is widely used in applications such as vehicle routing, scheduling, resource allocation, and other large-scale combinatorial optimization problems.
Problem Classes and Applicability
Large Neighborhood Search (LNS) is particularly well-suited to problems with solutions that have a structured representation that can be partially modified while preserving feasibility. These include many Mixed-Integer Programming (MIP) models, Constraint Programming (CP) problems, and classical combinatorial optimization problems.
The method is frequently applied to problems such as routing, timetabling, and workforce scheduling, where solutions consist of assignments, sequences, or sets of decisions that can be partially reoptimized.
LNS can also be combined with exact optimization techniques. For example, the repair step may involve solving a smaller Linear Programming (LP), Mixed-Integer Linear Programming (MILP), or Constraint Programming (CP) subproblem. Because of this hybrid nature, LNS is often considered a form of matheuristic, combining heuristic search with exact optimization methods.
Core Idea and Algorithmic Principle
Large Neighborhood Search (LNS) starts with a feasible solution, which may be generated by a heuristic construction method or another optimization procedure. Each iteration then proceeds in two main phases:
Destroy phase: A subset of the current solution is removed or relaxed. For example, in a routing problem, several customer visits might be removed from existing routes. This creates a partial solution where some decisions remain fixed while others are left unspecified.
Repair phase: The algorithm reconstructs the missing part of the solution by solving a subproblem. This step may rely on heuristic insertion strategies or on exact optimization techniques such as constraint propagation or Mixed-Integer Programming.
Because a relatively large part of the solution is reconsidered at each iteration, LNS can move between distant regions of the search space while still exploiting structure from the current solution.
Variants and Extensions
The effectiveness of LNS depends on how the neighborhoods are defined and how the destroy and repair phases are implemented. Many variants adapt the size and selection of neighborhoods dynamically. One well-known extension is Adaptive Large Neighborhood Search (ALNS), in which multiple destroy-and-repair strategies compete and are selected based on past performance.
LNS is also closely related to other neighborhood-based methods such as Variable Neighborhood Search (VNS) and local search, but differs in its emphasis on large-scale modifications combined with partial reoptimization.
Role in Modern Optimization Solvers
Large Neighborhood Search (LNS) has become a key technique in practical optimization, particularly for large and highly structured problems. By combining heuristic exploration with exact subproblem solving, LNS can produce high-quality solutions even when exact global optimization methods such as Branch-and-Bound or Branch-and-Cut become computationally challenging.
As a result, LNS is widely used in hybrid optimization frameworks and industrial solvers that integrate multiple search strategies.
Further Reading and References
Shaw, P. (1998). Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems. Proceedings of CP 1998.
One of the earliest papers introducing the Large Neighborhood Search concept.
Pisinger, D., & Ropke, S. (2010). Large Neighborhood Search. In Handbook of Metaheuristics, Springer.
A comprehensive overview of LNS techniques and their applications.
Talbi, E.-G. (2009). Metaheuristics: From Design to Implementation. Wiley.
Provides a broader context for LNS within modern metaheuristic frameworks.