| Issue |
RAIRO-Oper. Res.
Volume 35, Number 4, October December 2001
|
|
|---|---|---|
| Page(s) | 383 - 394 | |
| DOI | https://doi.org/10.1051/ro:2001120 | |
| Published online | 15 August 2002 | |
A New Relaxation in Conic Form for the Euclidean Steiner Problem in ℜ
1
Universidade Federal do Rio de Janeiro, Instituto de
Matemática, Departamento de Ciência da Computação,
Caixa Postal 68530, Rio de Janeiro, RJ 21945-970, Brazil; fampa@cos.ufrj.br.
2
Universidade
Federal do Rio de Janeiro, COPPE, Programa de Engenharia de
Sistemas e Computação, Caixa Postal 68511, Rio de Janeiro, RJ
21945-970, Brasil; maculan@cos.ufrj.br.
Received:
May
2000
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.
Key words: Euclidean Steiner tree problem / conic form / interior point algorithms.
© EDP Sciences, 2001
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.