MILP formulations and quantitative analysis for the core node location problem

We consider combinatorial problems arising in the design of optical networks. Given a set of requests between edge nodes, a set of potential locations for core nodes, and a prescribed number of core nodes, the task is to find paths for edge node requests to either minimize the maximal distance between two adjacent nodes, or to minimize the maximal path length, subject to the Quality of Service (QoS) constraint implemented as the maximal hop length. The same model can also be seen as a hub-and-spoke model where the core nodes are hubs and the edge nodes are spokes. The purpose of the computational study is to offer some indications on the complexity of the problem, and on factors such as problem size, variability in link lengths, and different objectives.