Introduction: One of the common applications of hub median and flow optimization problem is telecommunication network. These networks have terminals that have two types of information traffic demand: sending and receiving. Many telecommunication network designs have structures where information is collected at a lower level before it is sent to an upper level. Although several designs are possible, the problem we study is concentrator location problem with a bi-level structure with direct links from terminal nodes to concentrators at the lower level and direct links from concentrators to the central node at the upper level. Since both of the levels can be illustrated as a figure which seems like a star, this structure is called star-star network. Purpose: In this research, a branch and cut algorithm is developed for the introduced telecommunication network problem with bi-hierarchical star-star design where fixed identical concentrator capacities are assumed. The problem attempts to minimize the total of costs associated with location of concentrators, assignment of terminal nodes to those concentrators and routing of information traffic, while the solution space is subject to capacity and demand. Scope: After providing a mathematical formulation for the problem and suggesting an algorithm as a solution technique, experiments are carried out to evaluate the performance of the algorithm for some 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. Limitations: In this study, the experimented problems have 6, 8 and 10 nodes (except the central node) combined with four different concentrator capacities. Method: The bi-hierarchical star-star network problem is formally defined by a mixed integer linear programming formulation, then a branch and cut technique is applied to solve the test instances. For node selection in the branch and cut algorithm, we apply a depth first search strategy, while we apply two strategies in branching: either choosing a variable arbitrarily or choosing the variable whose value is closest to a specified value. A well known commercial solver, CPLEX, is used for solving continuously linear sub-problems generated throughout the algorithm. Since solving problems with large size may require longer solution times, some cutting planes are added to the original formulation, which makes it stronger. Findings: Results show that, addition of the valid inequalities has significant effect on all of the test instances. It has been observed that, when branching selection is made due to a specified value, most of the problem instances give smaller solution times compared to the the other branching strategy. Conclusion: A branch and cut algorithm is applied for capacitated concentrator location problem with star-star network design. Experiment has shown that the considered valid inequalities have significant effect on the solution time. Moreover, we have observed that the application of selection strategies decreases the solution times. For the future study, we consider that some other polyhedral improvement strategies such as adding minimal cover inequalities to the model may contribute to the reduction of solution time.
Anahtar Kelimeler: Telecommunication Network, Branch and Cut, Integer Programming