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 a two-level concentrator access network, each terminal has to be connected to a first-level concentrator, which in turn must be connected to a second-level concentrator. If no extra complicating constraints are taken into account, the problem, translated into the language of discrete location theory, amounts to an extension to two levels of facilities of the simple plant location problem. A straightforward formulation can be used, but we propose a more complicated model involving more variables and constraints. We show that the linear programming relaxations of both formulations have the same optimal values. However, the second formulation can be tightened by using a family of polyhedral cuts that define facets of the convex hull of integer solutions. We develop a Lagrangian relaxation method to compute lower bounds on the optimal value of the linear programming formulations and feasible solutions of the integer programming model. A simulated annealing algorithm is also designed to improve upon some of the upper bounds returned by the Lagrangian relaxation algorithm. Experiments show the effectiveness of the formulation incorporating polyhedral cuts and of an approach combining a Lagrangian relaxation method and a simulated annealing algorithm.