Mixed integer nonlinear optimizationmodels for the Euclidean Steiner tree problem in Rd

被引:0
作者
Ouzia, Hacene [1 ]
Maculan, Nelson [2 ,3 ]
机构
[1] Sorbonne Univ, CNRS, LIP 6, F-75005 Paris, France
[2] Univ Fed Rio de Janeiro, COPPE, BR-21941972 Rio De Janeiro, Brazil
[3] Univ Fed Rio de Janeiro, IM, BR-21941972 Rio De Janeiro, Brazil
关键词
Integer Programming; Euclidean Steiner tree problem; Steiner tree; Nonlinear optimization models; Mixed integer nonlinear optimization; Relaxation; MINIMAL-TREES;
D O I
10.1007/s10898-021-01001-6
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
New mixed integer nonlinear optimization models for the Euclidean Steiner tree problem in d-space (with d >= 3) will be presented in this work. All models feature a nonsmooth objective function but the continuous relaxations of their set of feasible solutions are convex. From these models, four convex mixed integer linear and nonlinear relaxations will be considered. Each relaxation has the same set of feasible solutions as the set of feasible solutions of the model from which it is derived. Finally, preliminary computational results highlighting the main features of the presented relaxations will be discussed.
引用
收藏
页码:119 / 136
页数:18
相关论文
共 18 条
[1]   A Novel Approach to Phylogenetic Tress: d-Dimensional Geometric Steiner Tress [J].
Brazil, M. ;
Thomas, D. A. ;
Nielsen, B. K. ;
Winter, P. ;
Wulff-Nilsen, C. ;
Zachariasen, M. .
NETWORKS, 2009, 53 (02) :104-111
[2]   On the history of the Euclidean Steiner tree problem [J].
Brazil, Marcus ;
Graham, Ronald L. ;
Thomas, Doreen A. ;
Zachariasen, Martin .
ARCHIVE FOR HISTORY OF EXACT SCIENCES, 2014, 68 (03) :327-354
[3]   PHYLOGENETIC ANALYSIS - MODELS AND ESTIMATION PROCEDURES [J].
CAVALLISFORZA, LL ;
EDWARDS, AWF .
EVOLUTION, 1967, 21 (03) :550-+
[4]   On a nonconvex MINLP formulation of the Euclidean Steiner tree problem in n-space: missing proofs [J].
D'Ambrosio, Claudia ;
Fampa, Marcia ;
Lee, Jon ;
Vigerske, Stefan .
OPTIMIZATION LETTERS, 2020, 14 (02) :409-415
[5]   Using a conic formulation for finding Steiner minimal trees [J].
Fampa, M ;
Maculan, N .
NUMERICAL ALGORITHMS, 2004, 35 (2-4) :315-330
[6]  
Fampa M., 2001, RAIRO, V35, P283
[7]  
Fampa M., 2019, DISCRETE APPL MATH
[8]   An improved algorithm for computing Steiner minimal trees in Euclidean d-space [J].
Fampa, Marcia ;
Anstreicher, Kurt M. .
DISCRETE OPTIMIZATION, 2008, 5 (02) :530-540
[9]   An overview of exact algorithms for the Euclidean Steiner tree problem in n-space [J].
Fampa, Marcia ;
Lee, Jon ;
Maculan, Nelson .
INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, 2016, 23 (05) :861-874
[10]   A specialized branch-and-bound algorithm for the Euclidean Steiner tree problem in n-space [J].
Fampa, Marcia ;
Lee, Jon ;
Melo, Wendel .
COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2016, 65 (01) :47-71