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.

In this paper, we present a new mathematical programming formulation for the euclidean Steiner Tree Problem (ESTP) in ${\Re }^{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},
zbl = {1020.90042},
mrnumber = {1896578},
language = {en},
url = {http://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
DA  - 2001///
SP  - 383
EP  - 394
VL  - 35
IS  - 4
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/RO_2001__35_4_383_0/
UR  - https://zbmath.org/?q=an%3A1020.90042
UR  - https://www.ams.org/mathscinet-getitem?mr=1896578
LA  - en
ID  - RO_2001__35_4_383_0
ER  - 
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://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 1315703 | Zbl 0833.90087

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

[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 1412228 | Zbl 0885.68088

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

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

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

[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 ${\Re }^{n}$: A mathematical programming formulation. Ann. Oper. Res. 96 (2000) 209-220. | MR 1802523 | Zbl 0966.90064

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

[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 1342935 | Zbl 0843.90088

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

[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 1479612 | Zbl 0885.68074