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

In this paper, we consider a problem relevant to the telecommunications ind ustry. 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 take n into account, the problem, translated into the language of discrete locat ion theory, amounts to an extension to two levels of facilities of the simp le plant location problem (SPLP). A straightforward formulation can be used , but we propose a more complicated model involving more variables and cons traints. We show that the linear programming relaxations of both formulatio ns have the same optimal values. However, the second formulation can be tig htened by using a family of polyhedral cuts that define facets of the conve x hull of integer solutions. We develop a Lagrangian relaxation method to c ompute lower bounds on the optimal value of the linear programming formulat ions and feasible solutions of the integer programming model. A simulated a nnealing algorithm is also designed to improve upon some of the upper bound s returned by the Lagrangian relaxation algorithm. Experiments show the eff ectiveness of the formulation incorporating poly-hedral cuts and of an appr oach combining a Lagrangian relaxation method and a simulated annealing alg orithm.