Optimisation Models and Methods.- A Supply Chain Network Perspective for Electric Power Generation, Supply, Transmission, and Consumption.- Worst-Case Modelling for Management Decisions under Incomplete Information, with Application to Electricity Spot Markets.- An Approximate Winner Determination Algorithm for Hybrid Procurement Mechanisms Logistics.- Proximal-ACCPM: A Versatile Oracle Based Optimisation Method.- A Survey of Different Integer Programming Formulations of the Travelling Salesman Problem.- Econometric Modelling and Prediction.- The Threshold Accepting Optimisation Algorithm in Economics and Statistics.- The Autocorrelation Functions in SETARMA Models.- Trend Estimation and De-Trending.- Non-Dyadic Wavelet Analysis.- Measuring Core Inflation by Multivariate Structural Time Series Models.- Financial Modelling.- Random Portfolios for Performance Measurement.- Real Options with Random Controls, Rare Events, and Risk-to-Ruin.
The Threshold Accepting Optimisation Algorithm in Economics and Statistics (p. 109-110)
Peter Winker1 and Dietmar Maringer2
1 Faculty of Economics, University of Giessen
2 CCFEA, University of Essex
Summary. Threshold Accepting (TA) is a powerful optimisation heuristic from the class of evolutionary algorithms. Using several examples from economics, econometrics and statistics, the issues related to implementations of TA are discussed and demonstrated. A problem speci.c implementation involves the de.nition of a local structure on the search space, the analysis of the objective function and of constraints, if relevant, and the generation of a sequence of threshold values to be used in the acceptance-rejection-step of the algorithm. A routine approach towards setting these implementation speci.c details for TA is presented, which will be partially data driven. Furthermore, .ne tuning of parameters and the cost and bene.t of restart versions of stochastic optimisation heuristics will be discussed.
Key words: Heuristic optimisation, threshold accepting
1 Introduction
Threshold accepting is an optimisation heuristic. Reasonable features of such optimisation heuristics include the following (Barr et al., 1995, p. 12). Firstly, they should aim at good approximations to the global optimum. Secondly, they should be robust to changes in problem characteristics, tuning parameters and changes in the constraints. Thirdly, they should be easy to implement to many problem instances, including new ones. Finally, a necessary requirement is that the solution approach consists of a procedure which does not depend on individual subjective elements. We will try to demonstrate that a suitable implementation of threshold accepting ful.lls these requirements. Threshold accepting is a modi.cation of the more often used simulated annealing (Kirkpatrick et al., 1983) using a deterministic acceptance criterion instead of the probabilistic one in simulated annealing. It also belongs to the class of local search methods (Aarts and Lenstra, 1997, p. 2). A classi.- cation of optimisation heuristics can be found in Winker and Gilli (2004), and a more detailed description of the threshold accepting algorithm is provided by Winker (2001).
Classical or standard optimisation techniques such as Newton's method are mostly based on di.erential calculus and .rst order conditions. However, this strategy requires the search space Ù to be continuous and to have just one global optimum. Many of the problems arising in statistics and economics exhibit objective functions with several local optima or discontinuities. A classi.cation of optimisation problems and some references to such cases are provided by Winker and Gilli (2004). Applied on these problems, classical optimisation techniques might report the local optimum next to the starting point - provided it was able to converge in the .rst place. It therefore seems adequate to extend the portfolio of optimisation techniques applied in these .elds by optimisation heuristics. There are a large number of problems in economics and statistics, including Maximum Likelihood Estimations, GMM, numerical models in economics, e.g., for computable general equilibrium models or quantitative game theory (Judd, 1998, pp. 133. and 187., respectively), which are documented, for which standard optimisation approaches may fail to provide solutions at all or would require tremendous amounts of computing resources. E.g., (Brooks et al., 2001) found that commonly used econometric software may fail for a rather simple maximum likelihood estimation for the parameters of a GARCH model whereas threshold accepting is capable of .nding signi.cantly better results as Maringer (2005) reports. Therefore, the question as to whether new optimisation paradigms could be useful in economics and statistics has to be answered by a clear-cut "yes".
During the last 15 years, threshold accepting has been successfully applied to many di.erent problems ranging from classical operations research to economics and statistics. In fact, the algorithm has been introduced with an application to the famous traveling salesman problem by Dueck and Scheuer (1990). It appears that simulated annealing is still more widespread in its use, but there exist also a number of implementations of threshold accepting both in traditional operational research applications and for more speci.c problems from economics and statistics. The second implementation of threshold accepting, described by Dueck and Wirsching (1991), covers multi- constraint 0-1 knapsack problems and has been included in a comparative study by Hana. et al. (1996). Some further early applications in the area of operational research are cited in the bibliography provided by Osman and Laporte (1996, p. 547). A more recent survey is provided in Winker (2001).
