A two-phase algorithm and performance bounds for the star-star concentrator location problem

The introduction of concentrators in a centralized telecommunication network provides a cost-effective way to connect the network. The star-star (SS) network model is considered, and the star-star concentrator location problem (SSCLP) is then examined. The SSCLP is NP-complete and can be formulated as a 0-1 integer programming problem. A two-phase algorithm is developed to solve the SSCLP. In the first phase, dualizing the side constraints produces a Lagrangian problem that is easy to solve and has an optimal value that is a lower bound (for minimization problems) on the optimal value of the original SSCLP. Heuristics then are applied to produce an upper bound (feasible solution) to the SSCLP. In the second phase, a branch-and-bound method is used to refine the solution space to obtain a tighter lower bound. First, an enumeration heuristic is applied to improve the best feasible solution obtained from the first phase. Then, a procedure for deriving bounding problems is presented and various branching strategies are discussed. Computational examples with up to 100 terminals and 30 potential concentrators are considered. All the network designs obtained are shown to be within 2% of optimal