Upper and lower bounds for the two‐level simple plant location problem

P. Chardaire, J.‐L. Lutton and A. Sutter

Annals of Operations Research, 1999, vol. 86, issue 0, 117-140

Abstract: In this paper, we consider a problem relevant to the telecommunications industry. In atwo‐level concentrator access network, each terminal has to be connected to a first‐levelconcentrator, which in turn must be connected to a second‐level concentrator. If no extracomplicating constraints are taken into account, the problem, translated into the language ofdiscrete location theory, amounts to an extension to two levels of facilities of the simpleplant location problem (SPLP). A straightforward formulation can be used, but we proposea more complicated model involving more variables and constraints. We show that the linearprogramming relaxations of both formulations have the same optimal values. However, thesecond formulation can be tightened by using a family of polyhedral cuts that define facetsof the convex hull of integer solutions. We develop a Lagrangian relaxation method tocompute lower bounds on the optimal value of the linear programming formulations andfeasible solutions of the integer programming model. A simulated annealing algorithm isalso designed to improve upon some of the upper bounds returned by the Lagrangian relaxationalgorithm. Experiments show the effectiveness of the formulation incorporating poly‐hedralcuts and of an approach combining a Lagrangian relaxation method and a simulatedannealing algorithm. Copyright Kluwer Academic Publishers 1999

Date: 1999
References: Add references at CitEc
Citations: View citations in EconPapers (11)

Downloads: (external link)
http://hdl.handle.net/10.1023/A:1018942415824 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:86:y:1999:i:0:p:117-140:10.1023/a:1018942415824

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1023/A:1018942415824

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().