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...
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)