scientific article; zbMATH DE number 1183278

From MaRDI portal
Publication:3838009





In practice many large-scale combinatorial optimization problems cannot be solved to optimality or near-optimality, since the search for a solution requires a prohibitive amount of time. One is forced to use approximation algorithms or heuristics for which usually a guarantee of the quality of the solution is missing, but for which polynomial runtime bounds are known. Thus, knowledge of the quality of the solution is traded off against computational time. Simulated annealing (SA), the main topic of this thesis, is such a heuristic. It is a generally applicable tool that combines local search with randomization techniques. There are numerous experimental comparisons of SA to several other heuristics. SA has proved to be very successful in these experiments. It produces in most cases the best solutions, even when applied to many different optimization problems. In contrast to the many experimental results, only very little is known about the theoretical performance of SA in finite time so far. The research focused on asymptotic convergence results in the last decade. But, asymptotic results are rather uninteresting for real-word problems. Finite time bounds, however, are of special interest for practical applications. The objective of this thesis is to study theoretically the behavior of SA in general, and of different applications of SA in particular. Thus, we try to explain the excellent practical results from a theoretical point of view and to improve the applicability of SA by a better understanding of the underlying mechanism. We give a new proof of the asymptotic convergence of SA in general. It is based on recent developments on the theory of rapidly mixing Markov chains. This proof technique enables us to give a considerably better finite time bound of the SA algorithm than known before. Taking this performance bound as a starting point, we show by two examples that, in general, this bound cannot be improved significantly. This is proved by the drift analysis of certain stochastic processes showing that the expected first hitting time of an optimal state in these examples is approximately of the same size as our finite time bound. Because it turns out that the performance bounds within reach are rather poor for practical purposes, additionally, we study the behavior of SA on random instances. In contrast to our worst-case examples mentioned above random instances are more suitable to explain the excellent performance results of SA on real-world instances. We present an algorithm using mainly SA-type techniques and a separation step that is able to solve the GCP on balanced random instances with high probability in sublinear time. This time bound beats every known randomized or deterministic algorithm for this random instances. Additionally, it is the first proof of the convergence of SA in polynomial time in the inhomogeneous case. To overcome the disadvantages of the balanced random model, we study the performance of a modified version of our algorithm in the general unbalanced case. Here, we are able to show SA to be an optimal state with high probability within \(O(n^{2+\varepsilon})\) steps, where \(n\) is the problem size and \(\varepsilon> 0\) arbitrarily small.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3838009)