ii. Heuristic Optimization

For optimization (“marathon”) problems where no exact algorithm fits (AtCoder Heuristic Contest, Topcoder Marathon, Google Hash Code, partial-scoring tasks): search the solution space, mostly stochastically, and keep the best thing found.

current = initial_solution(); best = current
while time remains:
    candidate = perturb(current)
    if accept(candidate, current): current = candidate
    if score(current) > score(best): best = current

Three design decisions: the neighbourhood (what perturb does), the acceptance rule, and the evaluation (which must be fast, ideally incremental).

Method	Accepts
hill climbing	only improvements (accepting ties lets it drift across plateaus); steepest ascent evaluates all neighbours, first improvement takes the first improving random neighbour (usually faster)
random restarts	improvements; restart from a fresh random solution when stuck
simulated annealing	improvements always, worsenings with probability $e^{-\Delta /T}$
iterated local search	hill-climb to a local optimum, apply a big random kick, hill-climb again, keep the better: remarkably strong for its simplicity, often beats plain annealing
tabu search	the best neighbour, but forbids recently reversed moves
beam search	keeps the best $k$ partial solutions per step
genetic algorithms	population, crossover, mutation
MCTS	tree search guided by rollout statistics: Game Search
threshold accepting, Great Deluge	deterministic relatives: accept moves under a threshold instead of a probability
parallel tempering (replica exchange)	several chains at different temperatures, periodically swapping states
adaptive cooling	adjust the schedule from the observed acceptance rate
quantum annealing	physical analogue, tunnelling instead of thermal fluctuation

Simulated annealing is the default: short, robust, almost no tuning beyond the temperature schedule.

What actually matters (ranked by impact)

1. Incremental evaluation. Computing $\Delta$ in $O(1)$ instead of rescoring in $O(n)$ multiplies the iteration count by $n$: nearly always the single biggest win.
2. The neighbourhood. Moves must be small enough to evaluate cheaply but large enough to escape local optima; mixing several move types usually beats one.
3. The time budget. Use the whole limit (about 90%, leave a margin); check the clock, not an iteration count (judges vary in speed), and only every 100–1000 iterations.
4. The temperature schedule. Geometric cooling from $T_0$ (accepting about half of the worsenings initially) to $T_1$ (accepting almost none).
5. The initial solution: a greedy start helps, but matters less than the above.

Problem type	Moves
permutation (TSP, scheduling)	swap two, 2-opt (reverse a segment), Or-opt (move a segment)
assignment	reassign one item, swap two assignments
subset selection	add, remove or swap one element
placement / layout	move one object, swap two, rotate
graph partition	move a vertex, swap a pair across the cut
continuous parameters	Gaussian perturbation with a shrinking radius

Escaping local optima	Idea
annealing	accept worsenings, decreasingly
random restarts	start over
perturbation / kicks	iterated local search
tabu list	forbid undoing recent moves
population	keep diverse solutions

Checklist. Seed from the clock for submissions (fixed seeds are useful while debugging); track the best-ever solution separately (the current state may be worse when time runs out); make moves undoable in $O(1)$ so rejection is free; precompute everything the evaluation needs; use a fast RNG (mt19937 or xorshift, never rand()); test several seeds (high variance means the search is not converging).

When heuristics are appropriate
the problem asks to maximize a score, partial / relative scoring	yes
$n$ is large and the problem is NP-hard, long time limit	yes
the checker verifies validity, not optimality	yes
the problem has a unique correct answer	no: a heuristic that is usually right is still WA

Code: generic annealing and TSP with 2-opt

// Generic simulated annealing (minimization) with geometric cooling per iteration.
template<class S, class Cost, class Neighbor>
S simulatedAnnealing(S cur, Cost cost, Neighbor neighbor, double T0, double rate, int iters, mt19937_64& rng) {
    S best = cur; double cc = cost(cur), bc = cc, T = T0;
    uniform_real_distribution<double> U(0, 1);
    for (int i = 0; i < iters && T > 1e-12; i++, T *= rate) {
        S nx = neighbor(cur, rng); double nc = cost(nx), d = nc - cc;
        if (d <= 0 || U(rng) < exp(-d / T)) { cur = nx; cc = nc; if (cc < bc) best = cur, bc = cc; }
    }
    return best;
}
 
double tourLength(const vector<vector<double>>& d, const vector<int>& t) {
    double s = 0; for (int i = 0; i < sz(t); i++) s += d[t[i]][t[(i + 1) % sz(t)]]; return s;
}
 
// 2-opt local search: reverse t[i+1..j] while it shortens the tour. Delta in O(1), application O(n).
void twoOpt(const vector<vector<double>>& d, vector<int>& t) {
    int n = sz(t); bool improved = true;
    while (improved) {
        improved = false;
        for (int i = 0; i + 1 < n; i++) for (int j = i + 2; j < n; j++) {
            int a = t[i], b = t[i + 1], c = t[j], e = t[(j + 1) % n];
            if (a == e) continue;                        // the two edges share a vertex
            double delta = d[a][c] + d[b][e] - d[a][b] - d[c][e];
            if (delta < -1e-12) { reverse(t.begin() + i + 1, t.begin() + j + 1); improved = true; }
        }
    }
}
 
// Time-based annealing for TSP with random 2-opt moves (the standard contest loop).
vector<int> annealTSP(const vector<vector<double>>& d, double seconds, double T0, double T1, mt19937_64& rng) {
    int n = sz(d); vector<int> t(n); iota(all(t), 0); shuffle(all(t), rng);
    double cur = tourLength(d, t), best = cur; vector<int> bt = t;
    auto start = chrono::steady_clock::now(); uniform_real_distribution<double> U(0, 1); double T = T0;
    for (long long it = 0;; it++) {
        if ((it & 255) == 0) {
            double el = chrono::duration<double>(chrono::steady_clock::now() - start).count() / seconds;
            if (el >= 1) break;
            T = T0 * pow(T1 / T0, el);                   // geometric cooling in time
        }
        int i = rng() % n, j = rng() % n; if (i > j) swap(i, j);
        if (j - i < 2 || (i == 0 && j == n - 1)) continue;
        int a = t[i], b = t[i + 1], c = t[j], e = t[(j + 1) % n];
        double delta = d[a][c] + d[b][e] - d[a][b] - d[c][e];
        if (delta <= 0 || U(rng) < exp(-delta / T)) {
            reverse(t.begin() + i + 1, t.begin() + j + 1); cur += delta;
            if (cur < best - 1e-12) best = cur, bt = t;
        }
    }
    return bt;
}

Proof: the 2-opt delta, termination, and what annealing guarantees

Delta. Reversing $t_{i+\mathrm{1..}j}$ keeps every edge inside the segment (traversed backwards, same length with symmetric distances) and replaces exactly the two boundary edges $(a,b),(c,e)$ by $(a,c),(b,e)$. Termination of 2-opt: every applied move strictly shortens the tour by more than $10^{-12}$ and there are finitely many tours, so the loop stops at a tour where no 2-opt move improves: a 2-opt local optimum.

Annealing at a fixed temperature. With a symmetric proposal $q(s,t)=q(t,s)$ and the Metropolis rule, the chain has stationary distribution $\pi (s)\propto e^{-c(s)/T}$: $\pi (s)P(s\to t)=q(s,t)\min (e^{-c(s)/T},e^{-c(t)/T})$ is symmetric in $s,t$ (detailed balance). As $T\to 0$ the ratio $\pi (s)/\pi (s^{\ast })=e^{-(c(s)-c(s^{\ast }))/T}$ vanishes for every non-optimal $s$, so the distribution concentrates on global optima. Hajek’s theorem (1988): with $T(k)\ge \frac{c}{\log k}$, $c$ at least the depth of the deepest local-optimum trap, the chain converges to the set of global optima in probability; cooling faster can leave it trapped with non-vanishing probability. Contest runs use geometric cooling and trade this guarantee for a good solution in the time budget. Checked: on random 8-city instances twoOpt always ends 2-opt-optimal, and the generic annealer and annealTSP reached the exact optimum (by enumeration) on all 60 tested instances.

Related notes

• Randomized Algorithms
• Hamiltonian Paths and TSP (exact Held–Karp)
• Approximation Algorithms (guaranteed ratios)