In the Generalized Quadratic Assignment Problem (GQAP), given M facilities and N locations, one must assign each facility to one location so as to satisfy the given facility space requirements, minimizing the sum of installation and facility interaction costs. In this paper, we propose a new Lagrangean relaxation and a lower bounding procedure for the GQAP. The new method allowed us to optimally solve 18 out of 19 instances from the literature with up to 35 facilities, 6 of which were open.