The ring/k-rings network design problem

I. Rodríguez Martín, J. J. Salazar González, H. Yaman

We address the problem of designing a two-level network where the upper level consists of a backbone ring network connecting the so-called hub nodes, and the lower level is formed by access ring networks that connect the non-hub nodes to the hub nodes. There is a fixed cost for each type of link, and a facility opening cost associated to each hub. The number of nodes in each access ring is bounded, and the number of access rings connected to a hub is limited to k, thus resulting in a ring/k-rings topology. The aim is to decide the hubs to open and to design the backbone and access rings to minimize the total cost. We propose a mathematical model, give valid inequalities, and describe a branch-and-cut algorithm to solve the problem. Computational results show the algorithm is able to find optimal solutions on instances involving up to 40 nodes within a reasonable time.

Palabras clave: Network design, valid inequalities, branch-and-cut.

L08.4 Optimización Lineal, Estocástica y Robusta
5 de septiembre de 2016  15:40
Aula 21.07

M. J. Gisbert Francés, M. J. Cánovas Cánovas, J. Parra López, F. J. Toledo Melero

M. Carrión, R. Dominguez Martin

F. J. Toledo Melero, M. J. Cánovas Cánovas, M. A. López-Cerdá, J. Parra López