local-search-and-neighborhoodslisted

# 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 d