Name
Title | ||
|---|---|---|
Formulations and branch-and-cut algorithm for the k-rooted mini-max spanning forest problem |
Abstract | ||
|---|---|---|
In this paper, we discuss two Integer Programming Formulations for the K-rooted Mini-max Spanning Forest Problem. In the first, connectivity is reinforced through Generalized Subtour Breaking inequalities while the second uses Directed cutset constraints. We implement a Branch-and-cut method based on the first formulation that also computes combinatorial lower bounds from the literature and implements a Linear Programming based multi-start heuristic. Our computational results suggest that the Linear Programming lower bounds compare favorably to combinatorial lower bounds. Instances generated as suggested in the literature were solved easily by the algorithms proposed in this study. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1007/978-3-642-21527-8_6 | INOC |
Keywords | Field | DocType |
computational result,linear programming,multi-start heuristic,forest problem,computes combinatorial,k-rooted mini-max,branch-and-cut algorithm,branch-and-cut method,k-rooted mini-max spanning forest,integer programming formulations,lower bound,generalized subtour,directed cutset constraint | Extreme point,Mathematical optimization,Heuristic,Branch and cut,Algorithm,Supply chain network,Integer programming,Linear programming,Linear programming relaxation,Mathematics,Dense graph | Conference |
Volume | ISSN | Citations |
6701 | 0302-9743 | 1 |
PageRank | References | Authors |
0.41 | 4 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alexandre Salles da Cunha | 1 | 242 | 22.32 |
| Luidi Simonetti | 2 | 152 | 15.82 |
| Abilio Lucena | 3 | 362 | 34.05 |