A branch and cut algorithm for the capacitated star-star telecommunication network problem

Abstract

In this study, a branch and cut algorithm is generated for a telecommunication network problem with bi-hierarchical star-star design and fixed identical concentrator capacities. The problem aims to find out how many and on which nodes concentrators should be located and how the terminal nodes should be assigned to those concentrators, in order minimize the total of costs associated with location, assignment and routing, subject to capacity and demand. Experiments are carried out to identify the performance of the algorithm for the problem instances with different number of total nodes and different concentrator capacities. The algorithm is also tested with additional valid inequalities and under different branching strategies in order to see their effect on the solution time. Experiments have shown that the considered valid inequalities and branching strategies have significant effect on the solution time.