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

Marcia Fampa; Nelson Maculan

RAIRO - Operations Research - Recherche Opérationnelle (2001)

  • Volume: 35, Issue: 4, page 383-394
  • ISSN: 0399-0559

Abstract

top
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.

How to cite

top

Fampa, Marcia, and Maculan, Nelson. "A new relaxation in conic form for the euclidean Steiner problem in $\Re ^n$." RAIRO - Operations Research - Recherche Opérationnelle 35.4 (2001): 383-394. <http://eudml.org/doc/105252>.

@article{Fampa2001,
abstract = {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 $\epsilon $-optimal solution for this latter problem using interior-point algorithm.},
author = {Fampa, Marcia, Maculan, Nelson},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {euclidean Steiner tree problem; conic form; interior point algorithms; Euclidean Steiner type tree problem},
language = {eng},
number = {4},
pages = {383-394},
publisher = {EDP-Sciences},
title = {A new relaxation in conic form for the euclidean Steiner problem in $\Re ^n$},
url = {http://eudml.org/doc/105252},
volume = {35},
year = {2001},
}

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
PB - EDP-Sciences
VL - 35
IS - 4
SP - 383
EP - 394
AB - 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 $\epsilon $-optimal solution for this latter problem using interior-point algorithm.
LA - eng
KW - euclidean Steiner tree problem; conic form; interior point algorithms; Euclidean Steiner type tree problem
UR - http://eudml.org/doc/105252
ER -

References

top
  1. [1] F. Alizadeh, Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM J. Optim. 5 (1995) 13-51. Zbl0833.90087MR1315703
  2. [2] E.N. Gilbert and H.O. Pollack, Steiner minimal trees. SIAM J. Appl. Math. 16 (1968) 323-345. Zbl0159.22001MR223269
  3. [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. Zbl0885.68088MR1412228
  4. [4] F.K. Hwang, A linear time algorithm for full Steiner trees. Oper. Res. Lett. 4 (1986) 235-237. Zbl0582.05022MR829887
  5. [5] F.K. Hwang and J.F. Weng, The shortest network under a given topology. J. Algorithms 13 (1992) 468-488. Zbl0764.68119MR1176673
  6. [6] F.K. Hwang, D.S. Richards and P. Winter, The Steiner Tree Problem. Ann. Discrete Math. 53 (1992). Zbl0774.05001MR1192785
  7. [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). Zbl1160.90639
  8. [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. Zbl0966.90064MR1802523
  9. [9] Y.E. Nesterov and M.J. Todd, Self-Scaled Barriers and Interior-Point Methods for Convex Programming (manuscript). Zbl0871.90064
  10. [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. Zbl0843.90088MR1342935
  11. [11] W.D. Smith, How to find Steiner minimal trees in Euclidean d -space. Algorithmica 7 (1992) 137-177. Zbl0751.05028MR1146493
  12. [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. Zbl0885.68074MR1479612

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.