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

Abstract

Abstract 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.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 102 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.