An exact algorithm for solving the ring star problem

作者：Kedad Sidhoum Safia; Viet Hung Nguyen^*

来源：Optimization, 2010, 59(1): 125-140.

DOI：10.1080/02331930903500332

• mixed integer programming
• polyhedral analysis
• branch-and-cut
• network design

This article deals with the ring star problem. It consists of finding a ring that goes through a central node and assigning every node not in the ring to a node in the ring so that the total design and assignment cost is minimized. We propose a new formulation based on the so-called st-chains which represent simple paths between two specific nodes s and t. We introduce new facet-defining inequalities and we develop an efficient branch-and-cut algorithm for the problem. Computational results that show the efficiency of our approach are presented.

• 出版日期2010