New Formulation of Simple Plant Location Problem (SPLP) and its Lagrangian Relaxation: Preliminary Computational Results

In this paper we give a new formulation of simple plant location problem (SPLP) that combines both strong and weak constraints. We relax the strong constraints and initiate the Lagrangian relaxation procedure. The resulting LP relaxation of the reduced problem is solved in O(n2 ) time to yield lower bounds that are significantly better than the bounds obtained by the LP relaxation of weak formulation of SPLP; and in attractive computational time. Our preliminary results show that this solution procedure has significant potential merit in solving SPLP by the branch and bound procedure