🧩 Constraint Solving POTD:Problem of the Day: Large Neighborhood Search (LNS) for Optimization

[github-actions[bot]]

Problem Statement

Large Neighborhood Search (LNS) is a meta-heuristic technique for solving hard combinatorial optimization problems by systematically exploring large regions of the solution space. Instead of making incremental moves like local search (changing one or two variables), LNS fixes most variables and re-optimizes a subset—the "neighborhood"—using an exact or heuristic method.

Concrete Instance

Consider a Vehicle Routing Problem (VRP) instance with 20 customers and 3 vehicles. In traditional local search, you might swap two customers between routes (a 1-exchange or 2-exchange move). With LNS, you might:

• Fix customers {1, 2, 3, 15, 16, 17} in their current routes
• Release the remaining 14 customers
• Re-optimize the released customers using constraint programming or MIP, creating better routes

This explores a much larger neighborhood than swapping individual customers.

Input/Output

• Input: A current solution (feasible or infeasible), instance data (costs, constraints)
• Output: An improved solution with lower objective value (cost, time, etc.) or proof that no improvement exists

Why It Matters

• Industrial Optimization: LNS is used in production scheduling, supply chain management, and fleet routing—problems where small local moves get stuck in mediocre local optima.
• Solver Integration: Modern solvers like Google OR-Tools and CPLEX use LNS as a core technique to bridge the gap between fast heuristics and slow exact methods.
• Scalability: LNS enables solving large instances (100–10,000 variables) that pure MIP or CP struggles with, by decomposing the problem into tractable subproblems.

Modeling Approaches

Approach 1: Large Neighborhood Search with MIP (Hybrid)

Treat LNS as a framework, not a model. At each iteration:

1. Partition: Divide decision variables into fixed (X_fixed, from current solution) and free (X_free, to be optimized)
2. Constrain: Add constraints that enforce X_i = solution[i] for all i ∈ fixed
3. Solve: Use MIP solver (CPLEX, Gurobi, or commercial solver) to optimize X_free, often with a time limit
4. Update: If improvement found, accept; otherwise diversify the neighborhood

Decision Variables:

• x[i] ∈ domain for each problem variable i
• N_size ∈ {5..50} for neighborhood size (tunable)

Constraints:

• Original problem constraints
• x[i] = solution[i] for all i not in neighborhood

Objective: Minimize/maximize original objective over free variables

Trade-offs:

• Strengths: Leverages powerful MIP solvers; excellent solution quality; principled framework
• Weaknesses: Expensive per iteration; requires commercial solver; tuning neighborhood size is critical

Example Pseudo-code (VRP with LNS)

procedure LargeNeighborhoodSearch(instance, timeLimit):
  solution := greedyConstruction(instance)
  best := solution
  elapsed := 0
  
  while elapsed < timeLimit:
    neighborhood := selectNeighborhood(solution, maxSize=15)
    fixed := solution \ neighborhood
    
    subproblem := createMIPSubproblem(instance)
    subproblem.addConstraints([x[i] = solution[i] for i in fixed])
    
    improved := solveMIP(subproblem, timeLimit=30s)
    
    if improved.cost < solution.cost:
      solution := improved
      if solution.cost < best.cost:
        best := solution
    else:
      neighborhood := selectNeighborhoodDiversified(solution, method="random")
    
    elapsed := elapsed + 30s
  
  return best

Approach 2: Decomposition with Constraint Programming

Use CP to model the subproblem, iteratively decomposing the problem:

1. Identify Critical Variables: Select a subset of "high-impact" variables (e.g., vehicle assignments, high-cost edges)
2. Branch & Fix: Assign some of these variables, fix others from the current solution
3. Propagate & Search: Use global constraints (cumulative, disjunctive) to propagate and search for improvement
4. Backtrack: If no improvement within resource limit, diversify and retry

Decision Variables:

• Same problem variables
• relax[i] ∈ {0,1} indicating if variable i is freed (0 = fixed)

Global Constraints:

• cumulative(task[], duration[], capacity) for resource-constrained scheduling
• disjunctive(task[]) for non-overlapping intervals
• element(index, array, value) for routing connections

Trade-offs:

• Strengths: Excellent propagation for structured problems (scheduling); flexible; can be tuned without expensive licenses
• Weaknesses: More expertise needed; may not scale as far as MIP for dense problems

Key Techniques

1. Neighborhood Selection Strategy

Choose which variables to free intelligently:

• Spatial: Free contiguous blocks (routing: consecutive customers in a tour)
• Cost-based: Free variables with largest reduced cost or slack in current solution
• Random: Occasionally sample random neighborhoods to escape local optima (critical for diversity)
• Adaptive: Learn which neighborhoods yield improvements; bias selection toward them

2. Subproblem Solution Strategy

Solving the subproblem efficiently is crucial:

• Time-limited MIP: Set aggressive time limits (10–60s) with good primal heuristics
• Approximate Subproblem: Relax some constraints in the subproblem for speed (e.g., drop certain side constraints temporarily)
• Warm-start: Initialize the subproblem solver with the current solution as a warm start
• Feasibility Restarts: If subproblem becomes infeasible, restore feasibility incrementally

3. Acceptance Criteria & Diversification

• First Improvement: Accept any solution better than current (fast, can get stuck)
• Best Improvement: Only accept strict improvement to best overall (slower, higher quality)
• Tabu/Penalty: Track recently explored neighborhoods and penalize revisiting them
• Restart: After k non-improving iterations, reset with a diversified neighborhood

Challenge Corner

Open Question for Readers:

1. Symmetry & Rotations: In a VRP with vehicles {A, B, C}, solutions where A and B are swapped represent the same objective value. How would you design a neighborhood selection strategy that accounts for this symmetry and avoids redundant reoptimizations?

2. Warm-starting Subproblems: Suppose your subproblem is a 0/1 knapsack and you've already solved it once with items {1..10}. In the next LNS iteration, you release item 11 and fix items {1..5}. What warm-start techniques from the first solve could accelerate the second?

3. Neighborhood Size Tuning: Empirically, larger neighborhoods yield better solutions but require more time per iteration. Design an adaptive algorithm that learns the Pareto frontier between solution quality and iteration time, and automatically adjusts neighborhood size.

References

1. Pisinger, D., & Ropke, S. (2010). "Large Neighborhood Search." Handbook of Metaheuristics (2nd ed.), Springer. A comprehensive survey of LNS variants with extensive bibliography.

2. Shaw, P. (1998). "Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems." CP-98 Principles and Practice of Constraint Programming, Springer. Seminal paper introducing LNS for VRP.

3. Balas, E., & Simonetti, N. (2001). "Linear Time Dynamic-Programming Algorithms for New Classes of Restricted TSPs." INFORMS Journal on Computing, 13(3). Shows structured LNS on restricted Traveling Salesman instances.

4. Google OR-Tools Documentation on [Local Search & LNS]((developers.google.com/redacted) Practical implementation guide with Python and C++ examples.

Warning

Firewall blocked 1 domain

The following domain was blocked by the firewall during workflow execution:

• awmgmcpg

To allow these domains, add them to the network.allowed list in your workflow frontmatter:

network:
  allowed:
    - defaults
    - "awmgmcpg"

See Network Configuration for more information.

Generated by 🧩 Constraint Solving — Problem of the Day · 6.86 AIC · ⌖ 18.5 AIC · ⊞ 5.2K · ◷

• expires on Jul 9, 2026, 4:12 AM UTC-08:00