Overview
Lin-Kernighan is a local search method for traveling salesperson improvement. It works by adaptively choosing k-edge exchanges that improve a tour.
SpecializedSource checked
Lin-Kernighan
Lin-Kernighan addresses traveling salesperson improvement by adaptively choosing k-edge exchanges that improve a tour.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Optimization
- Difficulty
- Advanced
- Family
- Local Search
- Tier
- Specialized
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 0
- Relationships
- 2
- Code example
- Not ready
- Visualization
- Ready
Core Concepts
traveling salesperson improvementlocal searchoptimization
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n^2)
Average
O(n^2)
Worst
O(n^3)
Space
O(n)
When to Use
- Use Lin-Kernighan when solving traveling salesperson improvement and you want to benefit from adaptively choosing k-edge exchanges that improve a tour.
- Choose it when O(n^2) average/worst-case time and O(n) memory match your workload profile.
- Prefer it over Held-Karp TSP or Christofides Algorithm when the problem structure favors traveling salesperson improvement.
When Not to Use
- Avoid when exact optimality is required but the method is heuristic or approximate.
- Avoid when constraints are poorly defined or cheap feasibility checks are unavailable.
What It Does
- Computes traveling salesperson improvement within Local Search workloads (O(n^2) time, O(n) space).
- Works by adaptively choosing k-edge exchanges that improve a tour.
- Maintains key invariants across traveling salesperson improvement, local search, optimization.
Use Cases
- Production and research workloads requiring traveling salesperson improvement via adaptively choosing k-edge exchanges that improve a tour.
- Local Search pipelines where O(n^2) time and O(n) space fit system constraints.
- Engineering comparisons against Held-Karp TSP and Christofides Algorithm when tuning traveling salesperson improvement.
Inputs
- Objective, constraints, and candidate variables
- Problem-specific costs or feasibility rules
Outputs
- Best known feasible solution
- Optimality or approximation result when available
Pseudocode
- 1.Formulate the traveling salesperson improvement instance, objective function, and initial candidate state or active search tree.
- 2.Evaluate candidate feasibility and objective bounds (traveling salesperson improvement, local search).
- 3.Advance the search by adaptively choosing k-edge exchanges that improve a tour.
- 4.Prune suboptimal branches, propagate unit/conflict clauses, or update incumbent best solutions.
- 5.Return the optimal or best-found feasible assignment once convergence or exhaustion is reached.
Canonical Example
- Input
- Objective, constraints, and candidate variables configured for a representative traveling salesperson improvement test case
- Output
- Best known feasible solution satisfying Lin-Kernighan invariants
- Explanation
- Lin-Kernighan processes the input by adaptively choosing k-edge exchanges that improve a tour, tracking traveling salesperson improvement and local search to produce the verified traveling salesperson improvement result.
Implementation Notes
- State the objective and feasibility checks in code before adding pruning.
- Keep incumbent solutions separate from bounds.
- Add tests for infeasible and exactly-tied cases.
Common Pitfalls
- Assuming a heuristic is exact without checking its guarantee.
- Using weak bounds that make search behave like brute force.
- Forgetting infeasible, empty, or degenerate constraint cases.
Interactive Mechanism Walkthrough
Iterative Convergence & State TrajectoryShow adaptively choosing k-edge exchanges that improve a tour on a small traveling salesperson improvement example.
Step 1 of 5: Formulate the traveling salesperson improvement instance, objective function, and initial candidate state or active search tree.
optimization-mechanismNotes
Lin-Kernighan operates in O(n^2) time and O(n) space within the Local Search family. Often compared with Held-Karp TSP and Christofides Algorithm.
Sources (2)
What each reference supports for this entry.
Lin-Kernighan TSP Heuristic
PaperOriginal reference for variable-depth k-opt local search for the traveling-salesman problem.
Open sourceThe Traveling Salesman Problem: A Computational Study
BookTSP reference for Lin-Kernighan's tour construction, local-search neighborhood, or heuristic tradeoffs.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageAlternative toHeld-Karp TSP
Lin-Kernighan and Held-Karp TSP are practical alternatives within traveling salesperson improvement, with different assumptions and tradeoffs.
Alternative toChristofides Algorithm
Lin-Kernighan and Christofides Algorithm are practical alternatives within traveling salesperson improvement, with different assumptions and tradeoffs.
Tags
Optimization