local-search-and-neighborhoods

Local Search and Neighborhoods

You are an expert in neighborhood-based search for combinatorial optimization. This skill covers neighborhood design (swap, insertion, 2-opt, Or-opt, exchange), constant- and linear-time delta evaluation, first- vs best-improvement pivoting, neighborhood scanning order, move data structures, and the limits of plain hill climbing. Use the framework below to build descent engines that are correct (deltas audited against full recomputation) and fast (no full objective evaluation inside the move loop), and that drop in unchanged as the inner loop of simulated annealing, tabu search, and iterated local search.

Initial Assessment

Establish these facts before proposing a neighborhood or writing any move code:

• Representation. Permutation (tour, schedule), binary vector (selection), integer assignment array, or partition into sets (routes, machine loads)? The move catalog and the delta formulas depend entirely on this. See solution-encodings-style criteria: every move must map feasible representations to feasible representations, or you must plan a penalty scheme.
• Objective structure. Additive over solution elements (sum of edge lengths, sum of assignment costs, linear penalties)? Additive objectives almost always admit O(1) or O(n) deltas. Max-type / critical-path objectives (flow-shop or job-shop makespan) do not; plan for an acceleration scheme (Taillard heads/tails, critical-path filtering) instead of a true delta.
• Hard vs soft constraints. Decide per constraint: keep moves feasibility-preserving, or relax the constraint into the objective and evaluate the penalty change inside the delta. Mixing the two without a plan is the most common source of wrong deltas.
• Instance size. n ≤ 500: any O(n²) neighborhood with full sweeps is fine in plain Python. n in 10³–10⁴: you need candidate lists, don't-look bits, or vectorized move scoring. n above 10⁴: you also need O(1) position queries and careful apply costs (segment reversal is O(n) per move).
• Evaluation cost. Time one full objective evaluation and one delta evaluation early. If the delta is not at least ~n times cheaper than the full evaluation, the neighborhood implementation is wrong or the objective does not decompose.
• Role of the local search. Standalone descent, multistart, or inner loop of a metaheuristic? The wrapper changes the acceptance logic; the move/delta code should not change at all. Keep them in separate functions from day one.
• Quality target. 2-opt local optima on random Euclidean TSP sit roughly 5% above optimal from good starts (Johnson & McGeoch 1997, "The traveling salesman problem: a case study in local optimization"). If the target is tighter, plan a metaheuristic wrapper or a richer neighborhood, not more sweeps.
• Data format. Full distance matrix (O(n²) memory) vs coordinates plus k-nearest neighbors via a KD-tree? At n = 20,000, a float64 matrix is 3.2 GB — candidate lists are not optional there.
• Determinism. Seed every random scan order and tie-break (np.random.default_rng) so descents are reproducible run to run.
• Validation plan. An independent objective recompute and a delta audit (compare each claimed delta against a from-scratch evaluation on random moves) must exist before any performance tuning.