Name
Title | ||
|---|---|---|
Stronger column generation bounds for the Minimum Cost Hop-and-root Constrained Forest Problem. |
Abstract | ||
|---|---|---|
In this paper, we present a Dantzig-Wolfe reformulation for the Minimum Cost Hop-and-root Constrained Forest Problem and discuss a Column Generation (CG) method to evaluate its Linear Programming (LP) bounds. For solving one of two types of pricing problems that arise in CG, we compared two solution strategies: Dynamic Programming and a Branch-and-cut (BC) algorithm. In general, CG performed much better when BC was used. Not only the LP bounds implied by the proposed reformulation are much stronger than the multi-commodity flow bounds from the literature, but also could be evaluated with less computational time. A Column Generation Heuristic was discussed and implemented, providing upper bounds that are, on average, within 2.3% of optimality. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.endm.2011.05.054 | Electronic Notes in Discrete Mathematics |
Keywords | Field | DocType |
Combinatorial optimization,Hop-constrained trees,Column Generation | Dynamic programming,Mathematical optimization,Column generation,Heuristic,Combinatorics,Combinatorial optimization,Linear programming,Hop (networking),Mathematics | Journal |
Volume | ISSN | Citations |
37 | 1571-0653 | 1 |
PageRank | References | Authors |
0.36 | 3 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dilson Lucas Pereira | 1 | 27 | 4.15 |
| Alexandre Salles da Cunha | 2 | 242 | 22.32 |
| Geraldo Robson Mateus | 3 | 413 | 42.30 |