Using multiflow formulations to solve the Steiner tree problem in graphs

被引：0

作者：

Bahiense, Laura ^{[1
]}

Besso, Arthur ^{[2
]}

Tostas, Rogerio ^{[1
]}

Maculan, Nelson ^{[1
]}

机构：

[1] Univ Fed Rio de Janeiro, Grad Sch & Res Engn, Alberto Luiz Coimbra Inst, Syst Engn & Comp Sci Program, Rio De Janeiro, Brazil

[2] IBGE Fdn CRM GEFET, Rio De Janeiro, Brazil

来源：

RAIRO-OPERATIONS RESEARCH | 2021年 / 55卷

关键词：

Steiner problem in graphs; multiflow formulations; linear relaxations;

D O I：

10.1051/ro/2020023

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We present three different mixed integer linear models with a polynomial number of variables and constraints for the Steiner tree problem in graphs. The linear relaxations of these models are compared to show that a good (strong) linear relaxation can be a good approximation for the problem. We present computational results for the STP OR-Library (J.E. Beasley) instances of type b, c, d and e.

引用

页码：S343 / S350

页数：8

共 13 条

[1] Solving Steiner tree problems in graphs with Lagrangian relaxation
Bahiense, L
Barahona, F
Porto, O
[J]. JOURNAL OF COMBINATORIAL OPTIMIZATION, 2003, 7 (03) : 259 - 282
[2] The volume algorithm revisited:: relation with bundle methods
Bahiense, L
Maculan, N
Sagastizábal, C
[J]. MATHEMATICAL PROGRAMMING, 2002, 94 (01) : 41 - 69
[3] AN ALGORITHM FOR THE STEINER PROBLEM IN GRAPHS
BEASLEY, JE
[J]. NETWORKS, 1984, 14 (01) : 147 - 159
[4] Besso, 2015, THESIS FEDERAL U RIO
[5] A CATALOG OF STEINER TREE FORMULATIONS
GOEMANS, MX
MYUNG, YS
[J]. NETWORKS, 1993, 23 (01) : 19 - 28
[6] Hwang F., 1992, ANN DISCRETE MATH, P53
[7] Karp R. M., 1972, IBM RES S SERIES, P85, DOI 10.1007/978-3-540-68279-0-8
[8] MACULAN N, 1988, MAT APL COMPUT, V7, P109
[9] Maculan N., 1987, ANN DISCRETE MATH, V31, P185
[10] Maculan N., 1983, PUBLICATIONS, V315

← 1 2 →