Cellular manufacturing is a promising approach for grouping efficiency in manufacturing systems. Although this problem has been extensively studied in the literature, very few authors have proposed exact methods. The basic cellular manufacturing problem consists in defining cells which lead to the minimum number of bottleneck elements. In this paper, we consider a new formulation of the cellular manufacturing problem where each variable corresponds to a potential cell. In order to deal with the large number of variables, we propose a solution scheme based on column generation techniques. We discuss its efficiency and compare it with other exact methods proposed in the literature.