A hub location problem with fully interconnected backbone and accesss networks

This paper considers the design of two-layered fully interconnected net-works. A two-layered network consists of clusters of nodes, each defining an access network and a backbone network. We consider the integrated problem of determining the access networks and the backbone network si-multaneously. A mathematical formulation is presented, but as the linear ∗Corresponding author 1 programming relaxation of the mathematical formulation is weak, a formu-lation based on the set partitioning model and column generation approach is also developed. The column generation subproblems are solved by solving a series of quadratic knapsack problems. We obtain superior bounds using the column generation approach than with the linear programming relax-ation. The column generation method is therefore developed into an exact approach using the Branch-and-Price framework. With this approach we are able to solve problems consisting of up to 25 nodes in reasonable time. Given the difficulty of the problem, the results are encouraging