Simulated annealing algorithm for the robust spanning tree problem |
| |
Authors: | Yury Nikulin |
| |
Institution: | 1.Institut für Betriebswirtschaftslehre,Christian-Albrechts-Universit?t zu Kiel,Kiel,Germany |
| |
Abstract: | This paper addresses the robust spanning tree problem with interval data, i.e. the case of classical minimum spanning tree
problem when edge weights are not fixed but take their values from some intervals associated with edges. The problem consists
of finding a spanning tree that minimizes so-called robust deviation, i.e. deviation from an optimal solution under the worst
case realization of interval weights. As it was proven in Kouvelis and Yu (Robust Discrete Optimization and Its Applications,
Kluwer Academic, Norwell, 1997), the problem is NP-hard, therefore it is of great interest to tackle it with some metaheuristic approach, namely simulated
annealing, in order to calculate an approximate solution for large scale instances efficiently. We describe theoretical aspects
and present the results of computational experiments. To the best of our knowledge, this is the first attempt to develop a
metaheuristic approach for solving the robust spanning tree problem. |
| |
Keywords: | Robust spanning tree Simulated annealing Uncertainty |
本文献已被 SpringerLink 等数据库收录! |
|