
Chained LK = iterated local search with LK as the descent and a double-bridge kick as the perturbation, accepting better-only. Warm starts make each iteration cheap. #algorithms #tsp Level 4 · Undergrad CS

Mgmt | Tech | Productivity posts. Catch-all of random thoughts.

Chained LK = iterated local search with LK as the descent and a double-bridge kick as the perturbation, accepting better-only. Warm starts make each iteration cheap. #algorithms #tsp Level 4 · Undergrad CS

Chained LK by numbers: best tour 100 → double-bridge kick (115) → LK → 96, adopt it. Kick again → 110 → LK → 94. Worse results are rejected, so the best only drops. #algorithms #tsp Level 3 · High-school

Chained LK escapes local optima with a double-bridge kick: cut the tour into A,B,C,D and reorder as A,C,B,D. Then re-run LK and keep the better tour. #algorithms #tsp Level 2 · ELI10

Stuck loop? Give it a special shake 🫨, untangle it again, and keep it only if it's shorter. Repeat thousands of times. That's chained Lin–Kernighan. #algorithms Level 1 · ELI5

Brute force sits at the bottom of the exact-TSP ladder at 2^Θ(n log n). Every exact method above it, from Held–Karp to Concorde, exploits structure it ignores. #algorithms #tsp Level 6 · Researcher

Brute force, formally: tours are orbits of the dihedral group, so there are (n−1)!/2 distinct ones. Symmetry buys a 2n× speedup, but it's still Θ(n!). #algorithms #tsp Level 5 · Graduate

Brute-force TSP: fix the start, enumerate (n−1)! permutations, score each in Θ(n). Total Θ(n!), guaranteed optimal, and hopeless past a dozen cities. #algorithms #tsp Level 4 · Undergrad CS

Six orders, six sums, one winner: A→B→D→C→A = 80 ✅ Brute force on a 4-city map is provably optimal because it checks every possible tour. #algorithms #tsp Level 3 · High-school

3 friends: 6 possible routes. 10 friends: 3.6 million. 15: over a trillion 🤯 Brute force tries them all and is guaranteed perfect, but only for tiny trips. #algorithms #tsp Level 2 · ELI10

Want the shortest route to visit your friends? Try every possible order and keep the best 🧭 Brute force always finds the perfect answer, just not quickly. #algorithms Level 1 · ELI5

Branch-and-cut is the exact frontier: Concorde proves optimal tours at 10⁴–10⁵ cities with comb, clique-tree and domino-parity cuts. Why it works so well is still open. #algorithms #tsp Level 6 · Researcher

Branch-and-cut is polyhedral combinatorics: the subtour polytope's LP value equals the Held–Karp bound (~1–2% off), and comb and clique-tree facets close the gap. #algorithms #tsp Level 5 · Graduate

TSP as an ILP (Dantzig–Fulkerson–Johnson 1954) has 2ⁿ subtour constraints. Branch-and-cut adds only violated ones, found by min-cut, and branches when stuck. #algorithms #tsp Level 4 · Undergrad CS

Two clusters, LP says "two triangles!" Add one subtour cut (≥ 2 edges must leave a cluster), re-solve, cut or branch on half-edges, stop when bound = tour. #algorithms #tsp Level 3 · High-school

Branch-and-cut solves a relaxed puzzle, spots how the answer cheats, and adds a rule that bans just that cheat. When cutting stalls, it branches. That's how big TSPs get solved. #algorithms #tsp Level 2 · ELI10

Your quick answer cheats by drawing little separate loops? Add a rule: no little loops! 🔪 Branch-and-cut keeps slicing away cheats until the perfect trip remains. #algorithms Level 1 · ELI5