An Empirical Evaluation of Stochastic Search Methods in Real-World Telecommunication Domains

In the literature there exist several stochastic methods for solving NP-hard optimization problems approximatively. Examples of such algorithms include (in the order of increasing computational complexity) stochastic greedy search methods, simulated annealing, and genetic algorithms. In this paper we are interested in the problem, which one of these methods is likely to give best performance in practice, with respect to the computational effort required in applying the method. We study this problem empirically by selecting a set of stochastic algorithms with varying computational complexity, and by experimentally evaluating for each method how the goodness of the results achieved improves with increasing computational time. For the evaluation, we use two practical optimization problems closely related to real-world problems in telecommunications. To get a wider perspective of the quality of the results, the stochastic methods are also compared against special-case greedy heuristics. Ou..