A New Relaxation in Conic Form for the Euclidean Steiner Problem in ℜ
Marcia Fampa, Nelson Maculan (2010)
RAIRO - Operations Research
Similarity:
In this paper, we present a new mathematical programming formulation for the Euclidean Steiner Tree Problem (ESTP) in ℜ. We relax the integrality constrains 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 interior-point algorithm.