Title | ||
---|---|---|
Exact solution approaches for the Multi-period Degree Constrained Minimum Spanning Tree Problem. |
Abstract | ||
---|---|---|
•It is shown that finding optimal multi-period minimum spanning trees is NP-hard.•A new formulation, at least as strong as the one in the literature, is introduced.•New valid inequalities introduced here strengthened our formulation even further.•Two exact methods combining Lagrangian Relaxation and Branch-and-cut are introduced.•Numerical results show that the new inequalities improve the algorithms’ performance. |
Year | DOI | Venue |
---|---|---|
2018 | 10.1016/j.ejor.2018.05.010 | European Journal of Operational Research |
Keywords | Field | DocType |
Combinatorial optimization,Lagrangian relaxation,Branch and cut,Multi-period spanning trees | Mathematical optimization,Time horizon,CPU time,Branch and cut,Combinatorial optimization,Integer programming,Degree-constrained spanning tree,Lagrangian relaxation,Mathematics,Minimum spanning tree | Journal |
Volume | Issue | ISSN |
271 | 1 | 0377-2217 |
Citations | PageRank | References |
0 | 0.34 | 11 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Rosklin Juliano Chagas | 1 | 0 | 0.34 |
Cristiano Arbex Valle | 2 | 40 | 4.90 |
Alexandre Salles da Cunha | 3 | 242 | 22.32 |