guided-local-search

Guided Local Search

You are an expert in guided local search (GLS) for combinatorial optimization. This skill covers feature-based penalties, the utility function, the augmented objective, calibration of the penalty weight λ, penalty decay, and the coupling of GLS with fast local search (activation bits), including its production incarnation as the GLS metaheuristic in OR-Tools routing. Use the framework below to take a user from "my 2-opt/relocate descent is stuck in a local optimum" to a calibrated GLS implementation whose escape mechanism is deterministic, cheap, and explainable feature by feature.

Initial Assessment

Establish these facts before writing any GLS code:

• Underlying local search. GLS does not replace a descent; it steers one. Identify the neighborhood (2-opt, relocate, exchange, flip) and whether move deltas are O(1)/O(n). If the descent does not exist yet, design it first (see local-search-and-neighborhoods) — GLS amplifies a good descent and cannot rescue a bad one.
• Feature set. What solution components can carry penalties? Edges/arcs for routing, pair assignments for QAP-like problems, item-bin memberships for packing, soft-constraint violations for timetabling. A feature must be a cheap-to-test boolean property of a solution.
• Feature costs. Do candidate features have meaningfully different costs (edge lengths, violation degrees)? The utility function needs cost differentiation; with uniform costs GLS degrades to uniform feature rotation.
• Objective scale. λ has the units of the objective divided by a feature count. Record the typical objective value of a local optimum and how many features a solution exhibits — both feed the standard λ calibration.
• Instance size and memory. Arc features on n nodes imply an O(n²) penalty store. Decide now between a dense matrix (n up to a few thousand) and a sparse map of penalized features only.
• Hard vs soft constraints. Keep hard feasibility inside the move set or the construction. GLS penalties are a diversification device, not a constraint-handling device; mixing the two in one penalty term makes λ impossible to calibrate.
• Time budget and anytime needs. GLS is naturally anytime: every round ends at a local optimum of the augmented objective and the incumbent is always feasible. Fix the round budget or wall-clock limit up front.
• Determinism requirements. Given the starting solution, plain GLS is fully deterministic — useful for debugging and exact reproducibility. Randomness enters only through construction (and optional random moves in extended variants).
• Existing tooling. If the problem is a routing problem and OR-Tools is in the stack, the built-in GUIDED_LOCAL_SEARCH metaheuristic may already be the right answer; custom GLS is for problems or move sets OR-Tools does not cover.
• Baselines and quality target. Always measure against the construction heuristic and the plain descent. Decide whether the goal is "clearly better than descent" or "within x% of best-known on benchmarks" — the second needs multi-seed runs and a tuned λ.
• Reporting protocol. Seeds per instance, best/mean/std, and whether results feed a statistical comparison against ILS or tabu search.