Computing Threshold Sequences


Enrico Schumann


Threshold Accepting

Review Status


Quantile-Based Methods

The threshold sequence in Threshold Accepting (TA) needs to be closely linked to the chosen definition of the neighbourhood. Larger neighbourhoods, which imply larger changes from one candidate solution to the next, should be accompanied by larger initial threshold values, and vice versa. Winker and Fang [1] suggested to obtain thresholds in a purely data-driven procedure; the pseudocode is given below.


In words: Select a large number $n_{\mathtt{Deltas}}$ of random solutions, and one neighbour for each. Then compute the absolute differences in the objective function between each pair. The thresholds are then descreasing quantiles of these changes. At the extreme (as in the given algorithm), every absolute difference constitutes one threshold. There is some evidence that starting the algorithm with a lower quantile improves the efficiency. Hence $n_{\mathtt{Deltas}}$ is usually greater than $n_{\mathtt{Rounds}}$.

A variant of this approach is have a ‘random walk’ through the data, see the following pseudocode ([2]).


Internal Links

Threshold Accepting
Related Articles

External links

1. Winker, P. and K. Fang (1997). Application of Threshold-Accepting to the Evaluation of the Discrepancy of a Set of Points. SIAM Journal on Numerical Analysis 34, 2028-2042.
2. Gilli, M., E. Kellezi and H. Hysi (2006). A Data-Driven Optimization Heuristic for Downside Risk Minimization. The Journal of Risk 8, 1-18, working paper available from SSRN.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License