Formulations and Branch-and-Cut Algorithm for the K-rooted Mini-Max Spanning Forest Problem

摘要

In this paper, we discuss two Integer Programming Formulations for the A"-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.