Kernighan–Lin Algorithm

The "champion heuristic" — chain together a sequence of swaps, then keep the best prefix.

Intuition

Why one swap isn't enough

Plain local search makes one swap, evaluates, accepts or rejects. The catch: some moves only look good after a few "neutral" or even bad swaps. KL says: commit to a sequence of swaps, record cumulative gain after each, then commit only to the prefix that gave the maximum cumulative gain.

This lets the search "tunnel through" a small barrier to reach a much better solution on the other side.

The algorithm

KL(initial solution, total cities N):
    repeat
        length ← random in [1, N]            // length of swap sequence
        cumulative ← []
        for counter = 0 .. length-1:
            pick random city c1 in current solution
            pick random city c2 ≠ c1
            swap c1 ↔ c2                     // do the swap (don't revert!)
            cumulative[counter] ← total gain so far (change in distance)
        K ← argmax over cumulative[0..length-1]    // the best prefix
        if cumulative[K] is an improvement:
            keep swaps 0..K, undo swaps K+1..length-1
        else:
            undo all swaps                            // back to start
    until no improvement found in a full pass

So if the sequence of cumulative gains was −2, −5, −2, +1, −3, +4, −1, you'd commit to the prefix ending at index 5 (gain = +4) — even though some intermediate steps made things worse.

Worked example (from your course)

TSP with 10 cities, starting tour length = 100 miles. Suppose length = 7 swaps. Track distance after each:

Index	0	1	2	3	4	5	6
Gain of this swap	−2	−3	+1	−3	+6	+4	+2
Cumulative distance	98	95	96	93	99	103	105

Cumulative distance is minimized at index 3 (93 miles, gain = −7). Commit those 4 swaps; undo the last 3. New starting solution: 93 miles.

Interactive demo

Run KL on a small TSP. The cumulative-gain chart shows why we cut at the best prefix.

Ready

Exam tips

Frequently asked

"Given a sequence of swap gains, find the prefix to keep" — compute cumulative sums, take the prefix where cumulative gain is most negative (for minimization).
"Why is KL stronger than simple local search?" — it can tunnel through worse intermediate states.
"Apply KL to graph coloring/CSP" — same structure: do swaps, record cumulative gain in # satisfied constraints, commit to the best prefix.
"What is the length parameter?" — number of consecutive swaps to evaluate before deciding.