A Hub Location Problem with Fully Interconnected Backbone and Accesss Networks 
Tommy Thomadsen, Jesper Larsen

Abstract  This paper considers the design of twolayered fully interconnected networks. A twolayered 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 simultaneously. A mathematical formulation is presented, but as the linear programming relaxation of the mathematical formulation is weak, a formulation 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 relaxation. The column generation method is therefore developed into an exact approach using the BranchandPrice 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. 
Keywords  Hierarchical networks, Fully interconnected networks, Hub location, BranchandPrice 
Type  Journal paper [With referee] 
Journal  Computers & Operations Research 
Year  2007 Month August Vol. 34 No. 8 pp. 25202531 
Publisher  Elsevier 
Note  Accepted for publication 
BibTeX data  [bibtex] 
IMM Group(s)  Operations Research 