Simulated annealing is a probabilistic optimization technique inspired by the physical process of annealing in metallurgy. In material science, heating a solid allows atoms to move freely into high-energy states; controlled cooling then permits the system to settle into a minimum energy configuration. This physical intuition translates directly to algorithmic design for finding global optima in complex search spaces.

Unlike deterministic methods such as hill climbing, which greedily ascend to the nearest local optimum, simulated annealing employs stochastic hill climbing with a probabilistic acceptance criterion. While hill climbing resembles a short-sighted climber who stops at the first peak encountered, simulated annealing behaves like a initially energetic explorer who can traverse valleys between peaks early in the process, gradually becoming more selective as "temperature" decreases, ultimate converging toward the global optimum.

The algorithm maintains a current solution and iteratively proposes neighboring states. Let $E_{current}$ and $E_{neighbor}$ represent the energy (cost) of current and candidate solutions respectively. The acceptance probability follows the Boltzmann distribution:

$$P(\text{accept}) = \exp\left(-\frac{\Delta E}{T}\right)$$

where $\Delta E = E_{neighbor} - E_{current}$ and $T$ is the current temperature. Better solutions ($\Delta E < 0$) are always accepted, while worse solutions may be accepted with probability decreasing as temperature lowers.

Implementation requires three hyperparameters: initial temperature $T_{init}$, cooling rate $\alpha$ (typically $0.95 < \alpha < 0.999$), and termination threshold $\epsilon$. The temperature update follows $T_{k+1} = \alpha \cdot T_k$.

#include <bits/stdc++.h>
using namespace std;

double evaluate(const vector<int>& state) {
    // Problem-specific objective function
    return 0.0;
}

void neighbor(vector<int>& state) {
    // Generate neighboring state by small perturbation
    int i = rand() % state.size();
    int j = rand() % state.size();
    swap(state[i], state[j]);
}

double simulated_annealing(vector<int> state) {
    double temperature = 10000.0;
    const double cooling = 0.995;
    const double epsilon = 1e-12;
    
    vector<int> current = state;
    double current_energy = evaluate(current);
    double best_energy = current_energy;
    
    while (temperature > epsilon) {
        vector<int> candidate = current;
        neighbor(candidate);
        double candidate_energy = evaluate(candidate);
        
        double delta = candidate_energy - current_energy;
        
        if (delta < 0 || exp(-delta / temperature) * RAND_MAX > rand()) {
            current = candidate;
            current_energy = candidate_energy;
            if (current_energy < best_energy) {
                best_energy = current_energy;
            }
        }
        
        temperature *= cooling;
    }
    
    return best_energy;
}

For time-critical applications, execute multiple annealing cycles within available runtime:

int main() {
    srand(time(nullptr));
    vector<int> initial_state = initialize();
    double global_best = evaluate(initial_state);
    
    while ((double)clock() / CLOCKS_PER_SEC < 0.95) {
        double local_best = simulated_annealing(initial_state);
        global_best = min(global_best, local_best);
    }
    
    cout << global_best << endl;
    return 0;
}

Balanced Partition Problem

Given $n$ integers, partition them into two subsets succh that the absolute difference of their sums is minimized. While dynamic programming provides exact solutions, simulated annealing offers an efficient heuristic for moderate constraints.

The state representation maintains the array configuration. The objective function computes $|\sum_{i \in S_1} a_i - \sum_{i \in S_2} a_i|$. Neighboring states are generated by swapping random elements between partitions.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const double COOLING = 0.9897;

ll compute_diff(vector<int>& arr, int n) {
    ll left = 0, right = 0;
    int mid = (n + 1) / 2;
    for (int i = 0; i < mid; ++i) left += arr[i];
    for (int i = mid; i < n; ++i) right += arr[i];
    return abs(left - right);
}

void annealing_pass(vector<int>& arr, int n, ll& best) {
    double temp = 5000.0;
    const double min_temp = 1e-15;
    
    while (temp > min_temp) {
        int i = rand() % n;
        int j = rand() % n;
        swap(arr[i], arr[j]);
        
        ll current = compute_diff(arr, n);
        ll delta = current - best;
        
        if (current < best) {
            best = current;
        } else if (exp((best - current) / temp) * RAND_MAX < rand()) {
            swap(arr[i], arr[j]); // Revert
        }
        
        temp *= COOLING;
    }
}

int main() {
    srand(time(nullptr));
    int cases;
    cin >> cases;
    
    while (cases--) {
        int n;
        cin >> n;
        vector<int> coins(n);
        for (int& x : coins) cin >> x;
        
        ll answer = LLONG_MAX;
        for (int iter = 0; iter < 1000; ++iter) {
            annealing_pass(coins, n, answer);
        }
        cout << answer << '\n';
    }
    return 0;
}

Variance Minimization

Consider an array where operations allow cyclic shifts that effectively swap adjacent difference elements. The optimal configuration exhibits a specific structure: the difference sequence first decreases then increases (unimodal).

After constructing this initial unimodal difference sequence via sorting, apply simulated annealing to the difference array $d$ where $d_i = a_i - a_{i-1}$. The objective minimizes population variance $\frac{1}{n}\sum_{i=1}^n (a_i - \bar{a})^2$, computed incrementally from the prefix sums of $d$.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const double COOLING_RATE = 0.935;
const int MAXN = 100005;

ll sequence[MAXN];
ll diff[MAXN];
int n;

ll calculate_variance() {
    ll prefix = 0;
    ll total = 0;
    for (int i = 1; i <= n; ++i) {
        sequence[i] = sequence[i-1] + diff[i];
        total += sequence[i];
    }
    ll mean = total * n;
    ll variance = 0;
    for (int i = 1; i <= n; ++i) {
        ll dev = sequence[i] * n - mean;
        variance += dev * dev;
    }
    return variance / n;
}

void optimize_variance(ll& best) {
    double temperature = 1000.0;
    const double threshold = 1e-17;
    
    while (temperature > threshold) {
        int i = rand() % (n - 1) + 2;
        int j = rand() % (n - 1) + 2;
        swap(diff[i], diff[j]);
        
        ll current = calculate_variance();
        ll delta = current - best;
        
        if (current < best) {
            best = current;
        } else if (exp((best - current) / temperature) < (double)rand() / RAND_MAX) {
            swap(diff[i], diff[j]);
        }
        
        temperature *= COOLING_RATE;
    }
}

int main() {
    srand(time(nullptr));
    cin >> n;
    
    for (int i = 1; i <= n; ++i) {
        cin >> sequence[i];
        diff[i] = sequence[i] - sequence[i-1];
    }
    
    // Initialize unimodal difference sequence
    sort(diff + 2, diff + n/2 + 1, greater<ll>());
    sort(diff + n/2 + 1, diff + n + 1);
    
    ll optimal = calculate_variance();
    
    while ((double)clock() / CLOCKS_PER_SEC < 0.95) {
        optimize_variance(optimal);
    }
    
    cout << optimal << endl;
    return 0;
}

Simulated annealing proves particularly effective for NP-hard problems including the Traveling Salesman Problem, geometric median (Fermat-Weber point) computation, and high-dimensional combinatorial optimization where exact algorithms fail to terminate within practical time limits.