Name
Title | ||
|---|---|---|
Branch-and-cut and hybrid local search for the multi-level capacitated minimum spanning tree problem. |
Abstract | ||
|---|---|---|
We propose algorithms to compute tight lower bounds and high quality upper bounds (UBs) for the multilevel capacitated minimum spanning tree problem. We first develop a branch-and-cut algorithm, introducing some new features: (i) the exact separation of cuts corresponding to some master equality polyhedra found in the formulation; (ii) the separation of Fenchel cuts, solving LPs considering all the possible solutions restricted to small portions of the graph. We then use that branch-and-cut within a GRASP that performs moves by solving to optimality subproblems corresponding to partial solutions. The computational experiments were conducted on 450 benchmark instances from the literature. Numerical results show improved best known (UBs) for almost all instances that could not be solved to optimality. (C) 2011 Wiley Periodicals, Inc. NETWORKS, Vol. 59(1), 148-160 2012 |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1002/net.20485 | NETWORKS |
Keywords | Field | DocType |
network design,branch-and-cut,fenchel cuts,MIP based local search | Capacitated minimum spanning tree,Combinatorics,Mathematical optimization,GRASP,Network planning and design,Branch and cut,Polyhedron,Spanning tree,Local search (optimization),Mathematics,Minimum spanning tree | Journal |
Volume | Issue | ISSN |
59 | SP1 | 0028-3045 |
Citations | PageRank | References |
4 | 0.47 | 19 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Eduardo Uchoa | 1 | 891 | 51.71 |
| Túlio A. Toffolo | 2 | 26 | 4.35 |
| Mauricio C. Souza | 3 | 135 | 11.20 |
| Alexandre X. Martins | 4 | 24 | 4.71 |
| ricardo fukasawa | 5 | 223 | 10.59 |