Premium
The Ring Star Problem: Polyhedral analysis and exact algorithm
Author(s) -
Labbé Martine,
Laporte Gilbert,
Martín Inmaculada Rodríguez,
González Juan José Salazar
Publication year - 2004
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.10114
Subject(s) - vertex (graph theory) , ring (chemistry) , algorithm , star (game theory) , integer programming , network planning and design , mathematics , integer (computer science) , computer science , mathematical optimization , graph , branch and cut , combinatorics , mathematical analysis , computer network , chemistry , organic chemistry , programming language
In the Ring Star Problem, the aim is to locate a simple cycle through a subset of vertices of a graph with the objective of minimizing the sum of two costs: a ring cost proportional to the length of the cycle and an assignment cost from the vertices not in the cycle to their closest vertex on the cycle. The problem has several applications in telecommunications network design and in rapid transit systems planning. It is an extension of the classical location–allocation problem introduced in the early 1960s, and closely related versions have been recently studied by several authors. This article formulates the problem as a mixed‐integer linear program and strengthens it with the introduction of several families of valid inequalities. These inequalities are shown to be facet‐defining and are used to develop a branch‐and‐cut algorithm. Computational results show that instances involving up to 300 vertices can be solved optimally using the proposed methodology. © 2004 Wiley Periodicals, Inc.