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

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