Loading...
Loading...

Go to the content (press return)

Solving the optimum communication spanning tree problem

Author
Zetina, C.; Contreras, I.; Fernandez, E.; Luna, C.
Type of activity
Journal article
Journal
European journal of operational research
Date of publication
2019-02
Volume
273
Number
1
First page
108
Last page
117
DOI
https://doi.org/10.1016/j.ejor.2018.07.055 Open in new window
Project funding
Discrete Optimization for Integrated Logistic and Transportation Problems
Repository
http://hdl.handle.net/2117/124689 Open in new window
URL
https://www.sciencedirect.com/science/article/abs/pii/S0377221718306775 Open in new window
Abstract
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...
Citation
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.
Keywords
Benders decomposition, Network optimization, Networks, Spanning trees
Group of research
GNOM - Mathematical Optimization Group

Participants

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