A Branch-and-Price Algorithm for the Ring-Tree Facility Location Problem

The ring-tree facility location problem is a generalization of the capacitated ring-tree problem in which additional cost and capacity related to facilities are considered. Applications of this problem arise in the strategic design of bi-level telecommunication networks. We investigate an extended integer programming formulation for the problem and different approaches to deal with the NP-hardness of the pricing problem that appears in a branch-and-price algorithm to solve it. Computational experiments show how heuristics and relaxations improved the performance of a branch-and-price algorithm.