Swap-vertex based neighborhood for Steiner tree problems
- Steiner tree problems (STPs) are very important in both theory and practice. In this paper, we introduce a powerful swap-vertex move operator which can be used as a basic element of any neighborhood search heuristic to solve many STP variants. Given the incumbent solution tree T, the swap-vertex move operator exchanges a vertex in T with another vertex out of T, and then attempts to construct a minimum spanning tree, leading to a neighboring solution (if feasible). We develop a series of dynamic data structures, which allow us to efficiently evaluate the feasibility of swap-vertex moves. Additionally, in order to discriminate different swap-vertex moves corresponding to the same objective value, we also develop an auxiliary evaluation function. We present a computational assessment based on a number of challenging problem instances (corresponding to three representative STP variants) which clearly shows the effectiveness of the techniques introduced in this paper. Particularly, as a key element of our KTS algorithm which participated in the 11th DIMACS implementation challenge, the swap-vertex operator as well as the auxiliary evaluation function contributed significantly to the excellent performance of our algorithm.
Metadaten| Author: | Zhang-Hua Fu, Jin-Kao Hao |
|---|
| DOI: | https://doi.org/10.1007/s12532-016-0116-8 |
|---|
| ISSN: | 1867-2949 |
|---|
| Parent Title (English): | Mathematical Programming Computation |
|---|
| Publisher: | Springer Science and Business Media LLC |
|---|
| Document Type: | Article |
|---|
| Language: | English |
|---|
| Year of Completion: | 2016 |
|---|
| Tag: | Software; Theoretical Computer Science |
|---|
| Volume: | 9 |
|---|
| Issue: | 2 |
|---|
| Page Number: | 24 |
|---|
| First Page: | 297 |
|---|
| Last Page: | 320 |
|---|
| Mathematical Programming Computation : | MPC 2017 - Issue 2 |
|---|