Carregant...
Carregant...

Vés al contingut (premeu Retorn)

Solving the optimum communication spanning tree problem

Autor
Zetina, C.; Contreras, I.; Fernandez, E.; Luna, C.
Tipus d'activitat
Article en revista
Revista
European journal of operational research
Data de publicació
2019-02
Volum
273
Número
1
Pàgina inicial
108
Pàgina final
117
DOI
https://doi.org/10.1016/j.ejor.2018.07.055 Obrir en finestra nova
Projecte finançador
Optimización discreta para problemas integrados en logística y transporte
Repositori
http://hdl.handle.net/2117/124689 Obrir en finestra nova
URL
https://www.sciencedirect.com/science/article/abs/pii/S0377221718306775 Obrir en finestra nova
Resum
This paper presents an algorithm based on Benders decomposition to solve the optimum communication spanning tree problem. The algorithm integrates within a branch-and-cut framework a stronger reformulation of the problem, combinatorial lower bounds, in-tree heuristics, fast separation algorithms, and a tailored branching rule. Computational experiments show solution time savings of up to three orders of magnitude compared to state-of-the-art exact algorithms. In addition, our algorithm is able t...
Citació
Zetina, C., Contreras, I., Fernandez, E., Luna, C. Solving the optimum communication spanning tree problem. "European journal of operational research", Febrer 2019, vol. 273, núm. 1, p. 108-117.
Paraules clau
Benders decomposition, Network optimization, Networks, Spanning trees
Grup de recerca
GNOM - Grup d'Optimització Numèrica i Modelització

Participants

  • Zetina, Carlos Armando  (autor)
  • Contreras Aguilar, Ivan  (autor)
  • Fernandez Areizaga, Elena  (autor)
  • Luna Mota, Carlos  (autor)