Tabu Search, in depth: short-term memory, aspiration, tenure, a hand-traced knapsack run and Python for bit-flip and 2-opt neighbourhoods

From hill climbing to tabu search

Local search needs three ingredients: a representation of a candidate solution, a neighbourhood that lists solutions one move away, and an objective. For 0/1 problems such as knapsack or max-cut, the solution is a bit vector and a move flips one bit. For a travelling-salesman tour, a move might be a 2-opt exchange that removes two edges and reconnects the tour. Hill climbing evaluates the neighbourhood and moves to the best improving neighbour until none exists.

Tabu search changes one rule: always move to the best admissible neighbour, improving or not. On its own that would oscillate: after stepping down from a peak, the best move is usually to step back up. The fix is short-term memory. After a move, its reverse, or more generally some attribute of it, becomes tabu for a number of iterations called the tenure. Storing attributes rather than whole solutions is cheap and strong: forbidding "flip bit 3 again" also forbids every solution that would need that flip.

Attributes over-restrict, though; they can forbid a move that leads somewhere new and excellent. The aspiration criterion overrides tabu status when a move would produce a solution better than the best found so far. Since that solution has never been visited, there is no cycling risk in taking it.

A complete implementation

Here is a complete implementation for bit-vector problems with a capacity constraint, using a penalty so the search can pass through infeasible states. Notice that the incumbent and the aspiration test only consider feasible solutions; otherwise a heavily overweight solution with a lenient penalty could be reported as the answer.

def tabu_search(values, weights, cap, start, tenure=2, penalty=10,
                max_iters=1000, patience=200):
    n = len(values)

    def score(x):
        v = sum(vi for vi, xi in zip(values, x) if xi)
        w = sum(wi for wi, xi in zip(weights, x) if xi)
        return v - penalty * max(0, w - cap), w <= cap, v

    x = list(start)
    best_x, best_v = None, float("-inf")
    s, feas, v = score(x)
    if feas:
        best_x, best_v = x[:], v
    tabu_until = [0] * n          # move i is tabu while it <= tabu_until[i]
    since_improve = 0
    for it in range(1, max_iters + 1):
        candidates = []
        for i in range(n):
            y = x[:]
            y[i] ^= 1
            s_y, feas_y, v_y = score(y)
            is_tabu = it <= tabu_until[i]
            aspires = feas_y and v_y > best_v
            if not is_tabu or aspires:
                candidates.append((s_y, -i, i, y, feas_y, v_y))
        if not candidates:
            break                 # everything tabu: stop or relax tenure
        s_y, _, i, y, feas_y, v_y = max(candidates)   # ties: lowest index
        x = y
        tabu_until[i] = it + tenure
        if feas_y and v_y > best_v:
            best_x, best_v = x[:], v_y
            since_improve = 0
        else:
            since_improve += 1
        if since_improve >= patience:
            break
    return best_x, best_v

This version re-scores every neighbour from scratch, which costs O(n) per neighbour and O(n squared) per iteration. Real implementations keep running totals and compute each move's delta in constant time, so an iteration is O(n). For large neighbourhoods they also use a candidate list, evaluating a sampled or pre-filtered subset of moves instead of all of them.

Worked example: escaping a knapsack local optimum

Take four items with value and weight A(10, 5), B(7, 4), C(6, 3) and D(5, 2), and capacity 9. The optimum is {B, C, D}: weight 9, value 18. A greedy start by value-to-weight ratio takes D, then A, then cannot fit C or B, giving {A, D} with value 15. With a penalty of 10 per unit of overweight, every single flip from {A, D} scores lower: adding C scores 21 - 10 = 11, adding B 22 - 20 = 2, dropping A 5, dropping D 10. Hill climbing stops here at 15. Tabu search, with tenure 2, continues. Running the code above prints exactly this trace:

Two lessons sit in this trace. The route to the optimum required giving up value twice, at iterations 1 and 3, which hill climbing never does. And the tabu list did the steering: at iteration 3 the obvious move back to {A, C, D} was forbidden, which forced the search into a new region of the space.

Tenure, long-term memory and richer attributes

Short-term memory prevents immediate cycling. Longer runs need two more mechanisms, both driven by long-term memory. Intensification returns to and searches more thoroughly around elite solutions, for example by restarting from the best few found and fixing the attributes they share. Diversification pushes the search into regions it has neglected, typically by keeping a frequency count of how often each attribute has been changed or held, and penalising frequent ones in the move score for a while.

Tenure choice matters more than anything else. Too short and the search cycles; too long and it forbids so much that it wanders with few admissible moves. Common practice ties tenure to problem size, on the order of the square root of n or a fixed fraction of n, and randomises it within a range each iteration. Taillard's robust tabu search for the quadratic assignment problem used exactly that random-range idea, and Battiti and Tecchiolli's reactive tabu search adjusts tenure automatically: when it detects repeated solutions, via hashing, it lengthens tenure; when the search stays repetition-free, it shortens it.

For permutation problems, attributes are richer. In 2-opt for the travelling salesman, a move removes edges (a, b) and (c, d) and adds (a, c) and (b, d). A common rule makes the removed edges tabu to re-add for the tenure.

def tour_length(tour, dist):
    return sum(dist[tour[k]][tour[(k + 1) % len(tour)]] for k in range(len(tour)))

def tabu_2opt(tour, dist, iters=5000, tenure=15):
    n = len(tour)
    cur, cur_len = tour[:], tour_length(tour, dist)
    best, best_len = cur[:], cur_len
    tabu = {}                               # edge (u, v) with u < v -> expiry
    for it in range(iters):
        move, move_delta = None, float("inf")
        for i in range(n - 1):
            for j in range(i + 2, n if i else n - 1):
                a, b, cc, d = cur[i], cur[i + 1], cur[j], cur[(j + 1) % n]
                delta = dist[a][cc] + dist[b][d] - dist[a][b] - dist[cc][d]
                added = [tuple(sorted(e)) for e in ((a, cc), (b, d))]
                is_tabu = any(tabu.get(e, -1) >= it for e in added)
                if is_tabu and cur_len + delta >= best_len:
                    continue                # aspiration: allow only if new best
                if delta < move_delta:
                    move, move_delta = (i, j, a, b, cc, d), delta
        if move is None:
            break
        i, j, a, b, cc, d = move
        cur[i + 1:j + 1] = reversed(cur[i + 1:j + 1])
        cur_len += move_delta
        for e in ((a, b), (cc, d)):         # removed edges may not come back
            tabu[tuple(sorted(e))] = it + tenure
        if cur_len < best_len:
            best, best_len = cur[:], cur_len
    return best, best_len

When to use it and what to compare against

Tabu search is deterministic given its tie-breaking, which makes runs reproducible and easy to debug, and it works well when good moves are cheap to evaluate exhaustively. Simulated annealing accepts worse moves at random with a temperature schedule; it needs less machinery but more iterations, and its behaviour is harder to reason about on a single run. Genetic algorithms search with a population and recombination, which helps when good solutions combine building blocks from different parents; see genetic algorithms. Many of the best modern solvers are hybrids, such as a genetic algorithm whose children are improved by tabu search.

None of these give optimality guarantees. When the instance is small enough, exact methods win: dynamic programming solves knapsack in pseudo-polynomial time, as in the knapsack problem, and Held-Karp solves small TSP instances exactly, as in TSP with dynamic programming. Use tabu search when the problem is NP-hard at the size you need, as discussed in NP-completeness, and a good answer in seconds beats a proven one in hours. Graph colouring is a classic success; Hertz and de Werra's TabuCol is a well-known example, and graph colouring covers the exact and greedy baselines to compare against.

In engineering practice tabu search shows up in shift and course timetabling, vehicle routing, job-shop scheduling, placement of replicas or shards across machines, and assigning ML training jobs to GPU nodes under memory, locality and fairness constraints, where each move reassigns one job and the objective blends utilisation and wait time.

Running it in production

Operational guidance for a production solver: time-box it and return the incumbent, because there is no natural end; log the best-value curve so you can see whether more time would help; seed it well with a greedy or previous-day solution, because a good start saves many iterations; and keep feasibility repair separate from scoring so constraint changes do not silently change behaviour. Tune the penalty weight adaptively: raise it when the search spends too long infeasible, lower it when it never crosses the boundary.

Failure modes are mostly about memory and evaluation. A tenure larger than the number of moves leaves nothing admissible and the loop stalls. Hashing collisions in reactive variants can trigger false cycle detection. Full re-scoring makes iterations too slow to matter, so incremental deltas are not optional at scale. Over-tuning parameters on one instance overfits; validate on a held-out set of instances, the same discipline you would apply to a model.