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.
Keywords: Steiner problem in graphs, multiflow formulations, linear relaxations
@article{RO_2021__55_S1_S343_0,
author = {Bahiense, Laura and Besso, Arthur and Tostas, Rogerio and Maculan, Nelson},
title = {Using multiflow formulations to solve the {Steiner} tree problem in graphs},
journal = {RAIRO. Operations Research},
pages = {S343--S350},
year = {2021},
publisher = {EDP-Sciences},
volume = {55},
doi = {10.1051/ro/2020023},
mrnumber = {4223131},
zbl = {1472.90106},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ro/2020023/}
}
TY - JOUR AU - Bahiense, Laura AU - Besso, Arthur AU - Tostas, Rogerio AU - Maculan, Nelson TI - Using multiflow formulations to solve the Steiner tree problem in graphs JO - RAIRO. Operations Research PY - 2021 SP - S343 EP - S350 VL - 55 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ro/2020023/ DO - 10.1051/ro/2020023 LA - en ID - RO_2021__55_S1_S343_0 ER -
%0 Journal Article %A Bahiense, Laura %A Besso, Arthur %A Tostas, Rogerio %A Maculan, Nelson %T Using multiflow formulations to solve the Steiner tree problem in graphs %J RAIRO. Operations Research %D 2021 %P S343-S350 %V 55 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ro/2020023/ %R 10.1051/ro/2020023 %G en %F RO_2021__55_S1_S343_0
Bahiense, Laura; Besso, Arthur; Tostas, Rogerio; Maculan, Nelson. Using multiflow formulations to solve the Steiner tree problem in graphs. RAIRO. Operations Research, Tome 55 (2021), pp. S343-S350. doi: 10.1051/ro/2020023
[1] , and , The volume algorithm revisited: relation with bundle methods. Math. Program. 94 (2002) 41–69. | MR | Zbl | DOI
[2] , and , Solving Steiner tree problems in graphs with lagrangian relaxation. J. Comb. Optim. 7 (2003) 259–282. | MR | Zbl | DOI
[3] , An algorithm for the Steiner problem in graphs. Networks 14 (1984) 147–159. | MR | Zbl | DOI
[4] , Problema de Steiner em grafos: Uma experiência numérica para problemas de médio porte utilizando formulações compactas de multi-fluxo. Master’s thesis. Programa de Engenharia de Sistemas e Computação, COPPE, Federal University of Rio de Janeiro, Rio de Janeiro (2015).
[5] and , Une nouvelle formulation du problème de Steiner sur un graphe orienté. In: Publication 315, Centre de Recherche sur les Transports, Université de Montréal, Montréal (1983).
[6] and , A catalog of Steiner tree formulations. Networks 23 (1993) 19–28. | MR | Zbl | DOI
[7] , and , The Steiner tree problem. In: Vol. 53 of Annals of Discrete Mathematics. North-Holland, Amsterdam (1992). | MR | Zbl
[8] , Reducibility among combinatorial problems, edited by , and . In: Complexity of Computer Computations. The IBM Research Symposia Series. Springer, New York, NY (1972) 85–103. | MR | Zbl
[9] , The Steiner problem in graphs. Ann. Discrete Math. 31 (1987) 185–211. | Zbl | MR
[10] , and , Le problème de Steiner sur un graphe orienté: formulations et relaxations. Comput. Appl. Math. 7 (1988) 109–118. | MR | Zbl
[11] , and , Integer linear models with a polynomial number of variables and constraints for some classical combinatorial optimization problems. Pesquisa Oper. 23 (2003) 161–168. | DOI
[12] , Implicit representation of generalized variable upper bounds in linear programming. Math. Program. 14 (1978) 11–20. | MR | Zbl | DOI
[13] , A dual ascent approach to Steiner tree problems on a directed graph. Math. Program. 28 (1984) 271–287. | MR | Zbl | DOI
Cité par Sources :
