  


Algorithms for the power$p$ Steiner tree problem in the Euclidean plane
Christina Burt(christina.naomi.burtgmail.com) 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 beadedMST heuristic satisfies $\sqrt{3}^{p1}(1+2^{1p})\leq \kappa\leq 3(2^{p1})$. We then provide two mixedinteger nonlinear programming formulations for the problem, and extend several important geometric properties into valid inequalities. Finally, we combine the valid inequalities with warmstarting and preprocessing to obtain computational improvements for the $p=2$ case. Keywords: Euclidean Steiner Tree Problem, Mixedinteger Quadratically Constrained Program, Heuristics Category 1: Combinatorial Optimization (Other ) Category 2: Nonlinear Optimization (Constrained Nonlinear Optimization ) Citation: Download: [PDF] Entry Submitted: 09/17/2015 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  