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 = {https://www.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  - https://www.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 https://www.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. https://www.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