zbMATH — the first resource for mathematics

Probabilistic tabu search algorithm for the multi-stage uncapacitated facility location problem. (English) Zbl 1020.90037
Fleischmann, Bernhard (ed.) et al., Operations research proceedings 2000. Selected papers of the symposium, OR 2000, Dresden, Germany, September 9-12, 2000. Berlin: Springer. 65-70 (2001).
Summary: A new probabilistic tabu search algorithm for discrete optimization problems is presented. The algorithm uses a randomized neighborhood with fixed threshold and applies adaptive rules to manage an active length of the tabu list. It is shown that the algorithm generates a finite aperiodic and irreducible homogeneous Markov chain on a suitable set of outcomes. This property guarantees asymptotic convergence of the best found solution to the global optimum. In order to estimate the real behavior of the algorithm, we consider the Multi-Stage Uncapacitated Facility Location Problem and present experimental results for hard benchmarks. A “big valley” conjecture is discussed as well.
For the entire collection see [Zbl 0988.00097].

90B80 Discrete location and assignment
90B40 Search theory