A new relaxation in conic form for the Suclidean Steiner problem in ℜn

In this paper, we present a new mathematical programming formulation for the Euclidean Steiner Tree Problem in ℜⁿ. We relax the integrality constraints on this formulation and transform the resulting relaxation, which is convex, but not everywhere differentiable, into a standard convex programming problem in conic form. We consider then an efficient computation of an ϵ-optimal solution for this latter problem using an interior-point algorithm.