Scaling Combinatorial Optimization via Large Neighborhood Search

47 concepts37 papers1 proposal

When faced with complex combinatorial problems—such as routing hundreds of delivery vehicles, scheduling factory floors, or planning paths for thousands of warehouse robots—algorithm designers encounter a fundamental barrier. Exact mathematical methods provide global optimality but collapse under exponential complexity at scale. Conversely, traditional local search methods scale well but easily get trapped in local minima because they only explore tiny, incremental changes (such as swapping two adjacent tasks).

Large Neighborhood Search (LNS) bridges this gap. Instead of building a solution from scratch or making minor tweaks, LNS operates via an iterative cycle of strategic destruction and targeted repair. By intentionally breaking a large chunk of a valid solution and re-optimizing just that isolated portion, LNS explores a massive "neighborhood" of alternative configurations while keeping the computational burden entirely manageable.

The Shift from Construction to Repair

To understand why LNS works, we must first look at how it reframes the optimization problem. Traditional solvers are often constructive: they build a solution variable by variable, frequently hitting dead ends and triggering expensive backtracking.

As demonstrated by Minton et al. (1990) with the min-conflicts heuristic, shifting the objective from building a flawless solution to repairing an initial, imperfect guess radically reduces computational overhead. Instead of navigating an empty search space, the algorithm starts with a complete assignment of variables and focuses its energy purely on resolving conflicts or reducing costs.

LNS formalizes this insight into a structured, two-phase loop often called ruin and recreate, a concept explored deeply by researchers like Van Hentenryck et al. (2011) and Breunig et al. (2016):

  1. Destroy: Take a fully formed, valid solution and deliberately unassign or remove a significant subset of its components (e.g., 15% to 30% of the variables).
  2. Repair: Use an optimization engine to fill in the resulting hole, finding the best possible configuration for the missing pieces while keeping the rest of the solution frozen.
[ Complete Solution ] ───( Destroy Phase )───> [ Broken Solution (Fixed Context) ]
         ▲                                                      │
         │                                                      ▼
         └───────────────( Repair Phase )───────────────────────┘

Standard local search operators, such as simple edge swaps or node relocations (Deng et al. 2018), only look one or two steps ahead. By contrast, the destroy-and-repair cycle allows the algorithm to leap across the solution space, bypassing the shallow local minima and global symmetries that typically stall simpler metaheuristics (Eiter et al. 2022).

Why It Works: The Power of Fixed Context

The core paradox of LNS is that it searches a larger neighborhood than traditional local search, yet it often runs much faster. Why doesn't this massive neighborhood cause a combinatorial explosion during the repair phase?

The secret lies in the fixed context. When LNS destroys a portion of a solution, it leaves the remaining 70% to 85% completely untouched. These untouched variables act as rigid, highly restrictive boundaries for the repair phase.

Because the sub-problem is tightly constrained by the surrounding solution, its search space is drastically compressed. This compression allows developers to deploy heavy-duty, exact optimization tools—such as Mixed-Integer Linear Programming (MILP) or Constraint Programming (CP) solvers—to find the absolute best repair for that specific hole.

For instance, Parmentier et al. (2024) demonstrated that using a MILP solver to optimally repair a destroyed routing plan allows the search to discover highly non-intuitive, cost-saving adjustments that heuristic rules would miss. Similarly, Geibinger et al. (2021) showed that fixing a large portion of an industrial schedule allows a constraint solver to instantly resolve high-dimensional sub-problems that would otherwise be computationally intractable if solved globally.

Strategic Destruction and Adaptivity

An LNS algorithm is only as good as its destroy operator. If you destroy variables completely at random, the repair phase will often just reconstruct the exact same solution you started with, wasting computational effort (Huang et al. 2023).

To make meaningful progress, the destruction must be structured. As Pacino (2011) notes, employing diverse removal strategies—such as targeting variables that are geographically close, clustered in the same window of time, or bound to the same over-utilized resource—forces the repair engine to find new, globally superior configurations.

Because different destroy and repair strategies excel at different stages of a search, modern implementations rarely rely on a single pair of operators. Instead, they use Adaptive Large Neighborhood Search (ALNS).

An ALNS framework maintains a portfolio of diverse destroy and repair heuristics. As the optimization progresses, the system dynamically adjusts the selection probability of each heuristic based on its historical performance in finding better solutions (Zhu et al. 2024). To eliminate the need for manual tuning, recent advancements by Cai et al. (2025) even treat this selection process as a Multi-Armed Bandit problem, using online learning to discover the optimal destroy-and-repair balance on the fly for each specific instance.

Case Study: Multi-Agent Path Finding

The elegance of the destroy-and-repair philosophy is vividly apparent in Multi-Agent Path Finding (MAPF), where hundreds of autonomous robots must navigate a shared environment without colliding. Planning optimal, collision-free paths for all agents simultaneously is an NP-hard problem that quickly paralyzes traditional pathfinders.

LNS solves this by turning the problem upside down. As detailed by Li et al. (2021), an LNS approach starts by planning an individual, optimal path for every agent completely independently, ignoring collisions entirely. This creates a complete but "messy" initial plan filled with conflicts.

[ Initial Plan: All agents take shortest paths (Many Collisions) ]
                               │
                               ▼
               ┌───────────────────────────────┐
               │  Select a subset of colliding │  <--- Destroy Phase
               │  agents & erase their paths   │
               └───────────────┬───────────────┘
                               │
                               ▼
               ┌───────────────────────────────┐
               │ Re-plan paths sequentially    │  <--- Repair Phase
               │ around the fixed agents       │
               └───────────────┬───────────────┘
                               │
                               ▼
[ Refined Plan: Collisions reduced or eliminated ]

The algorithm then enters its neighborhood refinement loop:

  • Destroy: It selects a small subset of agents whose paths intersect or cause bottlenecks and erases their trajectories.
  • Repair: It re-plans paths for only those selected agents, treating the paths of all other agents as moving, immutable obstacles.

By focusing exclusively on repairing localized spatial-temporal windows rather than re-solving the entire map, the computational complexity remains low. This iterative repair strategy scales remarkably well; Li et al. (2022) demonstrated that this exact framework can successfully coordinate up to 8,000 agents in highly congested warehouse environments, rapidly smoothing out conflicts that would stall traditional global solvers.

Key Foundational Work

Trees of Shortest Paths vs. Steiner Trees: Understanding and Improving Delete Relaxation Heuristics (2009) — contributed 2 concept elements to this direction.
Solving Large-Scale Constraint-Satisfaction and Scheduling Problems Using a Heuristic Repair Method (1990) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_large_neighborhood_search_6cefc1f7,
  title = {large neighborhood search},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/large-neighborhood-search/rdr_6cefc1f7dd6942af89937c0b999faf91},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_large_neighborhood_search_6cefc1f7_v1,
  title = {large neighborhood search},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/large-neighborhood-search/rdr_6cefc1f7dd6942af89937c0b999faf91/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake