Lagrangian relaxation for the star‐star concentrator location problem: Approximation algorithm and bounds

The star‐star concentrator location problem (SSCLP), which is a network layout problem, is considered. SSCLP is formulated as an integer linear programming problem. The Lagrangian relaxation (LR) method is used to obtain suboptimal solutions (upper bounds) and lower bounds. Three different LRs are used for SSCLP. The resulting Lagrangian dual problems are shown to be equivalent to some linear programming problems. An approximation algorithm is suggested for SSCLP that produces both a feasible solution (upper bound) and a lower bound. It is shown that if z and z̄are the lower and upper bounds found, then z̄/ z ≤ k , where k is the concentrator capacity. Some computational examples with up to 50 terminals and 20 potential concentrator sites are considered. All the network designs obtained are shown to be within 2.8% of optimal.