Premium
Lagrangian relaxation for the star‐star concentrator location problem: Approximation algorithm and bounds
Author(s) -
Mirzaian Andranik
Publication year - 1985
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230150102
Subject(s) - star (game theory) , lagrangian relaxation , concentrator , upper and lower bounds , relaxation (psychology) , lagrangian , linear programming relaxation , linear programming , integer programming , algorithm , mathematical optimization , mathematics , integer (computer science) , computer science , mathematical analysis , psychology , telecommunications , social psychology , programming language
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.