Volume 55, 2021Regular articles published in advance of the transition of the journal to Subscribe to Open (S2O). Free supplement sponsored by the Fonds National pour la Science Ouverte
|Page(s)||S343 - S350|
|Published online||02 March 2021|
Using multiflow formulations to solve the Steiner tree problem in graphs
Systems Engineering and Computer Science Program, Alberto Luiz Coimbra Institute – Graduate School and Research in Engineering, Federal University of Rio de Janeiro, Rio de Janeiro, Brazil.
2 IBGE Foundation – CRM/GEFET, Rio de Janeiro, Brazil.
* Corresponding author: firstname.lastname@example.org
Accepted: 21 February 2020
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.
Mathematics Subject Classification: 90C27 / 90Cxx / 90C90
Key words: Steiner problem in graphs / multiflow formulations / linear relaxations
© EDP Sciences, ROADEF, SMAI 2021
Initial download of the metrics may take a while.