Algorithms for the power-p Steiner tree problem in the Euclidean plane

Christina Burt, Alysson Costa, Charl Ras

Abstract


We study the problem of constructing minimum power-$p$ Euclidean $k$-Steiner trees in the plane. The problem is to find a tree of minimum cost spanning a set of given terminals where, as opposed to the minimum spanning tree problem, at most $k$ additional nodes (Steiner points) may be introduced anywhere in the plane. The cost of an edge is its length to the power of $p$ (where $p\geq 1$), and the cost of a network is the sum of all edge costs. We propose two heuristics: a ``beaded" minimum spanning tree heuristic; and a heuristic which alternates between minimum spanning tree construction and a local fixed topology minimisation procedure for locating the Steiner points. We show that the performance ratio $\kappa$ of the beaded-MST heuristic satisfies $\sqrt{3}^{p-1}(1+2^{1-p})\leq \kappa\leq 3(2^{p-1})$. We then provide two mixed-integer nonlinear programming formulations for the problem, and extend several important geometric properties into valid inequalities. Finally, we combine the valid inequalities with warm-starting and preprocessing to obtain computational improvements for the $p=2$ case.


Keywords


Steiner tree problem; Power-p; Mixed-integer formulations;Heuristics

Full Text:

PDF

References


GILBERT, E.; POLLAK, H. O. Steiner minimal trees. SIAM J. Appl. Math., v. 16, n. 1, p. 1–29, 1968.

KOU, G. M. L.; BERMAN, A. f. a. f. S. t. L. An efficient primal-dual interior-point method for minimizing a sum of euclidean norms. Acta inform., v. 15, n. 1, p. 141–145, 1981.

LAARHOVEN, J.; OHLMANN, J. A randomized delaunay triangulation heuristic for the euclidean steiner tree problem in rd . J. Heuristics, v. 17, n. 4, p. 353–372, 2011.

WINTER, P.; ZACHARIASEN, M. Euclidean steiner minimum trees: An improved exact algorithm. Networks, v. 30, n. 3, p. 149–166, 1997.

MACULAN, N.; MICHELON, P.; XAVIER, A. The euclidean steiner tree problem in rn: A mathematical programming formulation. Ann. Oper. Res., v. 96, n. 1–4, p. 209–220, 2000.

CONG, J. et al. Performance optimization of vlsi interconnect. Integr. VLSI j., v. 21, n. 1–2, p. 1–94, 1996.

MINOUX, M. Networks synthesis and optimum network design problems: Models, solution methods and applications. Networks, v. 19, n. 3, p. 313–360, 1989.

WENG, J.; THOMAS, D.; MAREELS, I. Maximum parsimony, substitution model, and probability phylogenetic trees. J. Comput. Biol., v. 18, n. 1, p. 67–80, 2011.

MONTENEGRO,F.;TORREA ̃O,J.;MACULAN, N. Microcanonical optimization for the euclidean steiner problem in rn with application to phylogenetic inference. Phys. Rev. E, v. 68, n. 5, p. 056702–1– 056702–5, 2003.

LAARHOVEN, J.; OHLMANN, J. S. lee and m. younis, recovery from multiple simultaneous failures in wireless sensor networks using minimum steiner tree. J. Parallel Distr. Com., v. 70, n. 5, p. 525–536, 2010.

BRAZIL, M. et al. Improving underground mine access layouts using software tools. Interfaces, v. 44, n. 2, p. 195–203, 2013.

GROTSCHEL, M.; MONMA, C.; STOER, M. Design of survivable communications networks. In: BALL et al. (Ed.). Network Models. 1. ed. London, UK: Elsevier, 1995, (Handbook of Management Science and Operations Research, v. 7). cap. 10, p. 617–672.

WARME, D.; WINTER, P.; ZACHARIASEN, M. Exact algorithms for plane steiner tree problems: A computational study. In: DU J.M. SMITH, J. R. D.-Z. (Ed.). Advances in Steiner trees. 1. ed. Massachusetts, USA: Kluwer Academic Publishers, 2000. v. 1, p. 81–116.

BERMAN, P.; ZELIKOVSKY, A. On approximation of the power-p and bottleneck steiner trees. In: DU

J.M. SMITH, J. R. Z. (Ed.). Advances in Steiner trees. 1. ed. Massachusetts, USA: Kluwer Academic Publishers, 2000. v. 71, p. 117––135.

WANG, L.; LI, Z. An approximation algorithm for a bottleneck k-steiner tree problem in the euclidean plane. Inform. Process. Lett., v. 81, n. 3, p. 151–156, 2002.

ANDERSEN, K. D. et al. An efficient primal-dual interior-point method for minimizing a sum of euclidean norms. SIAM J. Sci. Comput., v. 22, p. 243–262, 2000.

BRAZIL, M. et al. Generalised k-steiner tree problems in normed planes. Algorithmica, v. 71, n. 1, p. 66–86, 2015.

FAMPA, M.; MACULAN, N. A new relaxation in conic form for the euclidean steiner problem in Rn,. RAIRO-Oper. Res., v. 35, n. 4, p. 383–394, 2001.

ACHTERBERG, T. Scip: solving constraint integer programs. Math. Program. Comput., v. 1, n. 1, p. 1–41, 2009.

HART, W. et al. Pyomo–Optimization Modeling in Python. 1. ed. Berlin, Germany: Springer, 2012. v. 67.

BERTHOLD, T.; HEINZ, S.; VIGERSKE, S. Extending a cip framework to solve miqc. In: JON, L.; SVEN, L. (Ed.). Mixed Integer Nonlinear Programming. 1. ed. Berlin, Germany: Springer, 2012. v. 71, p. 427–444.

VIGERSKE, S. Decomposition of Multistage Stochastic Programs and a Constraint Integer Programming Approach to Mixed-Integer Nonlinear Programming. 2013.

IBM. Cplex Optimizer. Online. Dispon ́ıvel em: ⟨http://www-01.ibm.com/software/commerce/optimization/ cplex-optimizer⟩.

Gurobi Optimization. Gurobi. Online. Dispon ́ıvel em: ⟨http://www.gurobi.com/⟩.

Python Software Foundation. Python random library. Dispon ́ıvel em: ⟨https://docs.python.org/2/library/random. html⟩.

Gurobi Optimization. Gurobi Variable attributes: start. Online. Dispon ́ıvel em: ⟨http://www.gurobi.com/ documentation/6.0/refman/start.html⟩.

RESENDE, M.; RIBEIRO, C. Greedy randomized adaptative search procedures. In: GLOVER; G.KOCHENBERGER (Ed.). Massachusetts, USA: Kluwer Academic Publishers, 2003. p. 219–249.

Lourenc ̧o,H.;MARTIN,O.;STU ̈TZLE,T.Iterated local search. In: GLOVER, F.; KOCHENBERGER, G. (Ed.). Handbook of metaheuristics. 1. ed. Massachusetts, USA: Kluwer Academic Publishers, 2003. v. 70, p. 321–353.




DOI: https://doi.org/10.22456/2175-2745.80525

Copyright (c) 2018 Christina Burt, Alysson Costa, Charl Ras

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.