(Author to whom all correspondence should be addressed)

The Capacitated Facility Location Problem (CFLP) consists of locating a set of facili-ties with capacity constraints to satisfy the demands of a set of clients at the minimum cost. In this paper we propose a simple and effective heuristic for large-scale instances of CFLP. It is based on a Lagrangean relaxation, which is used to select a subset of “promising ” variables, forming the core problem, and on a Branch-and-Cut algorithm that solves the core problem. We report on computational experience showing that instances up to 2000 facilities and 2000 clients are solved to 1%-optimality in less than 8 minutes of CPU time on a personal computer