Annealing and replica exchange

Explore alternative contraction-tree structures with simulated annealing, or exchange search states across temperatures.

On this page

Local changes to a contraction tree

Simulated annealing and parallel tempering / replica exchange both start from an existing complete path. Local updates change how a few tree nodes are grouped without executing arrays.

Before rotation

After rotation

a, c, and d can each represent a subtree. Rotation changes how they are combined, not their internal structures.

These methods can temporarily accept higher-cost states while separately retaining the best path seen.

Simulated annealing

Higher temperatures make worse candidates easier to accept. As temperature falls, the search increasingly favors improvements. For energy increase $\Delta E$ , the Metropolis acceptance probability is:

p=\min\left(1,\exp\left[-\beta\Delta E\right]\right).

$\beta$ is inverse temperature. In treesa_path, the energy in this expression is $E=\log_2 J$ , where $J$ is the complete-path optimization objective. anneal_path instead computes acceptance from relative objective changes and relative temperature, so the same temperature parameters are not directly interchangeable.

pseudocode

current = initial tree
best = initial tree
Search over the temperature schedule:
    Repeat local updates:
        candidate = apply a local rotation to current
        Use the Metropolis criterion to decide whether to accept candidate
        If accepted, set current = candidate
        If current sufficiently improves best, set best = current
return best

anneal_path runs one chain; anneal_paths runs independent chains in parallel from the same starting point; treesa_path sweeps the tree at progressively increasing inverse temperatures. All return one best path.

Replica exchange

Multiple replicas search at different temperatures. After each round of local search, exchanges between adjacent-temperature states are attempted. This exchange step distinguishes the method from independently running several annealing chains.

P, Q, R, and S represent complete contraction trees. After an accepted exchange, search continues from the P and Q tree states at T₁ and T₀, respectively.

Temperature positions stay fixed; tree states are exchanged. P and Q accept the exchange, while R and S stay in place.

pseudocode

Initialize replicas at different temperatures from the starting path
Repeat search rounds until the round limit or stopping condition:
    Run local searches for all replicas in parallel
    Try swapping replica states at neighboring temperatures
    Update the best path seen so far
return the better of the historical best and best starting paths

Rotations within each replica are accepted based on relative objective changes. Exchanges between adjacent replicas use $E_i=\ln J_i$ and $\beta_i=1/T_i$ , with probability:

p_{\mathrm{swap}}= \min\left(1,\exp\left[(\beta_i-\beta_j)(E_i-E_j)\right]\right).

temper_path initializes every replica from the same path; temper_paths can initialize from multiple paths. The replica count is not the number of returned paths: both functions return only one.

Interfaces and local reconfiguration

Method	Interface
Simulated annealing	`anneal_path`, `anneal_paths`
Tree sweeps by inverse temperature	`treesa_path`
Replica exchange	`temper_path`, `temper_paths`

See the Rust API for complete parameters, temperature definitions, and stopping settings. These methods retain the best input as a fallback, but do not guarantee global optimality.

Periodic subtree reconfiguration

Local search in replica exchange can periodically invoke subtree reconfiguration. It directly solves a small local network, rather than performing a single tree rotation.

Download source Markdown ↓