euclidean steiner tree problem

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

  • Christina Burt
  • Alysson Machado Costa
  • Charl Ras
    • Categories Combinatorial Optimization, Constrained Nonlinear Optimization Tags , ,

    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 … Read more

    A specialized branch-and-bound algorithm for the Euclidean Steiner tree problem in n-space

  • Marcia Fampa
  • Jon Lee
  • Wendel Melo
    • Categories (Mixed) Integer Nonlinear Programming, Branch and Cut Algorithms Tags , , ,

    We present a specialized branch-and-bound (b&b) algorithm for the Euclidean Steiner tree problem (ESTP) in R^n and apply it to a convex mixed-integer nonlinear programming (MINLP) formulation of the problem, presented by Fampa and Maculan. The algorithm contains procedures to avoid difficulties observed when applying a b&b algorithm for general MINLP problems to solve the … Read more