A new relaxation in conic form for the euclidean Steiner problem in ℜ n
RAIRO - Operations Research - Recherche Opérationnelle, Tome 35 (2001) no. 4, pp. 383-394.

In this paper, we present a new mathematical programming formulation for the euclidean Steiner Tree Problem (ESTP) in ℜ n . 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.

Mots-clés : euclidean Steiner tree problem, conic form, interior point algorithms 
@article{RO_2001__35_4_383_0,
     author = {Fampa, Marcia and Maculan, Nelson},
     title = {A new relaxation in conic form for the euclidean {Steiner} problem in $\Re ^n$},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {383--394},
     publisher = {EDP-Sciences},
     volume = {35},
     number = {4},
     year = {2001},
     mrnumber = {1896578},
     zbl = {1020.90042},
     language = {en},
     url = {http://archive.numdam.org/item/RO_2001__35_4_383_0/}
}
TY  - JOUR
AU  - Fampa, Marcia
AU  - Maculan, Nelson
TI  - A new relaxation in conic form for the euclidean Steiner problem in $\Re ^n$
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2001
SP  - 383
EP  - 394
VL  - 35
IS  - 4
PB  - EDP-Sciences
UR  - http://archive.numdam.org/item/RO_2001__35_4_383_0/
LA  - en
ID  - RO_2001__35_4_383_0
ER  - 
%0 Journal Article
%A Fampa, Marcia
%A Maculan, Nelson
%T A new relaxation in conic form for the euclidean Steiner problem in $\Re ^n$
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2001
%P 383-394
%V 35
%N 4
%I EDP-Sciences
%U http://archive.numdam.org/item/RO_2001__35_4_383_0/
%G en
%F RO_2001__35_4_383_0
Fampa, Marcia; Maculan, Nelson. A new relaxation in conic form for the euclidean Steiner problem in $\Re ^n$. RAIRO - Operations Research - Recherche Opérationnelle, Tome 35 (2001) no. 4, pp. 383-394. http://archive.numdam.org/item/RO_2001__35_4_383_0/

[1] F. Alizadeh, Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM J. Optim. 5 (1995) 13-51. | MR | Zbl

[2] E.N. Gilbert and H.O. Pollack, Steiner minimal trees. SIAM J. Appl. Math. 16 (1968) 323-345. | MR | Zbl

[3] M.X. Goemans and D.P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 6 (1995) 1115-1145. | MR | Zbl

[4] F.K. Hwang, A linear time algorithm for full Steiner trees. Oper. Res. Lett. 4 (1986) 235-237. | MR | Zbl

[5] F.K. Hwang and J.F. Weng, The shortest network under a given topology. J. Algorithms 13 (1992) 468-488. | MR | Zbl

[6] F.K. Hwang, D.S. Richards and P. Winter, The Steiner Tree Problem. Ann. Discrete Math. 53 (1992). | MR | Zbl

[7] C. Lemaréchal and F. Oustry, Semidefinite relaxations and Lagrangian duality with application to combinatorial optimization. Rapport de recherche, Institut National de Recherche en Informatique et en Automatique, INRIA (1999).

[8] N. Maculan, P. Michelon and A.E. Xavier, The Euclidean Steiner Problem in ℜ n : A mathematical programming formulation. Ann. Oper. Res. 96 (2000) 209-220. | MR | Zbl

[9] Y.E. Nesterov and M.J. Todd, Self-Scaled Barriers and Interior-Point Methods for Convex Programming (manuscript). | Zbl

[10] S. Poljak, F. Rendl and H. Wolkowicz, A recipe for semidefinite relaxation for (0,1)-quadratic programming. J. Global Optim. 7 (1995) 51-73. | MR | Zbl

[11] W.D. Smith, How to find Steiner minimal trees in Euclidean d-space. Algorithmica 7 (1992) 137-177. | MR | Zbl

[12] G. Xue and Y. Ye, An Efficient Algorithm for Minimizing a Sum of Euclidean Norms with Applications. SIAM J. Optim. 7 (1997) 1017-1036. | MR | Zbl