Optimizing access to service based networks

We consider the problem of determining the optimal access topology to servi ce based networks. The problem is formulated as a concentrator location pro blem with a discontinuous piece wise linear objective function that depends on the traffic of the nodes that are homed to the concentrator. Five heuri stics are developed to solve the problem and are compared on an extensive s et of examples. Based on this comparison a combination heuristic utilizing a Lagrangian relaxation and swap drop add approach was found to give the be st solution in the minimal time.