A unified limited column generation approach for facility location problems on trees

In this paper, we show that several well-known facility location problems on trees, including the Uncapacitated Facility Location Problem (UFLP), the Facility Constrained Covering Problem (FCCP), the Customer Constrained Covering Problem (CCCP), the Round-Trip Covering Problem (RTCP), the p-Center Problem, and the p-Median Problem, can be formulated uniformly into a special structured Tree Partitioning Problem (TPP). Then, we develop a generic algorithm to solve all these facility location problems. Although our algorithm is a generic one, our time complexity for solving each of these problems matches the best time complexity of the ‘dedicated’ algorithm. We believe our approach has shown much insight into the location problems on trees.