This paper presents a novel algorithm for solving the cell assignment problem with special emphasis on energy awareness. The algorithm aims at finding the minimum number of base stations (BSs) that have to be turned on to guarantee the required service to the maximum number of users at lowest cost. The main contribution of the algorithm is the design of an effective solution that ensures an optimal assignment in a subset of base stations N ¿ N resulting in a drastic reduction of the search space within every subset N, eliminating the exponential growth over the number of users M, i.e. reducing the complexity from O(NM) to O(1). A branch-and-bound approach has been designed to determine the optimal base station assignments. Experiments demonstrate that our solution performs as expected in terms of profit, served clients, and energy savings due to active BSs, at the expense of very reasonable execution time overhead. Peer Reviewed