An improved algorithm for computing Steiner minimal trees in Euclidean \(d\)-space. (English) Zbl 1152.90663
Summary: We describe improvements to Smith’s branch-and-bound (B&B) algorithm for the Euclidean Steiner problem in \(\mathbb R^d\). Nodes in the B&B tree correspond to full Steiner topologies associated with a subset of the terminal nodes, and branching is accomplished by “merging” a new terminal node with each edge in the current Steiner tree. For a given topology, we use a conic formulation for the problem of locating the Steiner points to obtain a rigorous lower bound on the minimal tree length. We also show how to obtain lower bounds on the child problems at a given node without actually computing the minimal Steiner trees associated with the child topologies. These lower bounds reduce the number of children created and also permit the implementation of a “strong branching” strategy that varies the order in which the terminal nodes are added. Computational results demonstrate substantial gains compared to Smith’s original algorithm.
MSC:
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
| 90C27 | Combinatorial optimization |
References:
| [1] | Andersen, E. D.; Andersen, K. D., The MOSEK interior point optimizer for linear programming: An implementation of the homogeneous algorithm, (Frenk, H.; Roos, C.; Terlaky, T.; Zhang, S., High Performance Optimization. High Performance Optimization, Applied Optimization, 33 (1999), Kluwer Academic Publishers), See also · Zbl 1028.90022 |
| [2] | Andersen, K. D.; Christiansen, E.; Conn, A. R.; Overton, M. L., An efficient primal-dual interior-point method for minimizing a sum of Euclidean norms, SIAM J. Sci. Comput., 22, 1, 243-262 (2000) · Zbl 0966.65053 |
| [3] | Arora, S., Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems, J. ACM, 45, 5, 753-782 (1998) · Zbl 1064.90566 |
| [4] | Beasley, J. E., OR-Library: Distributing test problems by electronic mail, J. Oper. Res. Soc., 41, 1069-1072 (1990), See also |
| [5] | Cockayne, E. J.; Hewgill, D. E., Exact computation of Steiner minimal trees in the plane, Inform. Process. Lett., 22, 151-156 (1986) · Zbl 0593.05022 |
| [6] | Cockayne, E. J.; Hewgill, D. E., Improved computation of plane Steiner minimal trees, Algorithmica, 7, 2-3, 219-229 (1992) · Zbl 0756.05043 |
| [7] | Du, D.-Z.; Smith, W. D., Disproofs of generalized Gilbert-Pollak conjecture on the Steiner ratio in three or more dimensions, J. Combin. Theory A, 74, 1, 115-130 (1996) · Zbl 0856.05025 |
| [8] | Fampa, M.; Maculan, N., Using a conic formulation for finding Steiner minimal trees, Numer. Algorithms, 35, 315-330 (2004) · Zbl 1047.90055 |
| [9] | Garey, M. R.; Graham, R. L.; Johnson, D. S., The complexity of computing Steiner minimal trees, SIAM J. Appl. Math., 32, 4, 835-859 (1977) · Zbl 0399.05023 |
| [10] | Gilbert, E. N.; Pollack, H. O., Steiner minimal trees, SIAM J. Appl. Math., 16, 1-29 (1968) · Zbl 0159.22001 |
| [11] | Hwang, F. K., A linear time algorithm for full Steiner trees, Oper. Res. Lett., 4, 5, 235-237 (1986) · Zbl 0582.05022 |
| [12] | Hwang, F. K.; Richards, D. S.; Winter, W., The Steiner tree problem, Ann. Discrete Math., 53 (1992), Elsevier, Amsterdam · Zbl 0774.05001 |
| [13] | Hwang, F. K.; Weng, J. F., Hexagonal coordinate systems and Steiner minimal trees, Discrete Math., 62, 49-57 (1986) · Zbl 0601.05016 |
| [14] | K. Krishnan, G. Pataki, N. Gupta, T. Terlaky, Towards a practical simplex method for second order cone programming, Presentation at INFORMS Annual Meeting, Denver, 2004; K. Krishnan, G. Pataki, N. Gupta, T. Terlaky, Towards a practical simplex method for second order cone programming, Presentation at INFORMS Annual Meeting, Denver, 2004 |
| [15] | Lobo, M.; Vandenberghe, L.; Boyd, S.; Lebret, H., Applications of second-order cone programming, Linear Algebra Appl., 284, 193-228 (1998) · Zbl 0946.90050 |
| [16] | Linderoth, J. T.; Savelsbergh, M. W.P., A computational study of branch and bound search strategies for mixed integer programming, INFORMS J. Comput., 11, 173-187 (1999) · Zbl 1040.90535 |
| [17] | Maculan, N.; Michelon, P.; Xavier, A. E., The Euclidean Steiner problem in \(R^n\): A mathematical programming formulation, Ann. Oper. Res., 96, 209-220 (2000) · Zbl 0966.90064 |
| [18] | Melzak, Z. A., On the problem of Steiner, Canad. Math. Bull., 4, 2, 143-148 (1961) · Zbl 0101.13201 |
| [19] | Smith, W. D., How to find Steiner minimal trees in Euclidean \(d\)-space, Algorithmica, 7, 137-177 (1992) · Zbl 0751.05028 |
| [20] | Soukup, J.; Chow, W. F., Set of test problems for minimum length connection networks, ACM/SIGMAP Newslett., 15, 48-51 (1973) |
| [21] | W.D. Smith, J.M. Smith, On the Steiner ratio in 3-space. Working paper, Department of IEOR, University of Massachusetts, 1994; W.D. Smith, J.M. Smith, On the Steiner ratio in 3-space. Working paper, Department of IEOR, University of Massachusetts, 1994 |
| [22] | Warme, D. M.; Winter, P.; Zachariasen, M., Exact algorithms for plane Steiner tree problems: A computational study, (Du, D. Z.; Smith, J. M.; Rubinstein, J. H., Advances in Steiner Trees (2000), Kluwer Academic Publishers), 81-116 · Zbl 0968.90067 |
| [23] | Winter, P., An algorithm for the Steiner problem in the Euclidean plane, Networks, 15, 323-345 (1985) · Zbl 0586.90087 |
| [24] | Winter, P.; Zachariasen, M., Euclidean Steiner minimum trees: An improved exact algorithm, Networks, 30, 149-166 (1997) · Zbl 0893.90170 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
