In GSM-EDGE radio access network (GERAN), the assignment of base stations to base station controllers has a strong impact on network performance. In this paper, an exact method is proposed to improve an existing assignment of base stations to base station controllers. The aim is to minimize the number of handovers between base station controllers given a maximum number of base stations re-allocations. Results from a real case study show that the proposed method outperforms classical re-partitioning approaches in terms of solution quality.