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.

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