<p>The present work deals with the application of a novel Column Generation (CG) approach to the<br />Software Clustering Problem (SCP). In this problem, one has a Modular Dependence Graph (MDG)<br />consisting of a set V of nodes representing the modules of a software, a set E of edges, or the set<br />of relationships between two modules u, v ∈ V of the software, and each relationship has an associated<br />weight given by c_uv . The goal is to partition the MDG in clusters, and the quality of such partition<br />must be maximized. The quality of the partition is given by a measure called Modularization Quality<br />(MQ). To tackle this problem, we apply the Dantzig-Wolfe decomposition having a formulation from<br />literature as a starting point. Given this, we present two approaches based on CG: (i) the standard<br />CG approach, and (ii) a new approach, which we call Staged Column Generation (SCG). In this new<br />approach, at each stage, the problem is solved by CG considering a restricted version of the pricing<br />subproblem. At the last stage, the complete version of the subproblem is considered and CG runs<br />until convergence. In the context of the present work, in the last stage, the subproblems are solved by<br />MIP, and in the previous stages, the restricted subproblems are solved heuristically. In addition, we<br />present a heuristic procedure to initialize the Master Problem, aiming to improve the convergence of<br />the algorithms. We test our algorithms in a set of 47 instances found in literature. With the proposed<br />approaches we were able to improve the literature results solving all these instances to optimality (45<br />of them in the root node). Furthermore, the SCG approach presented a considerable performance<br />improvement in terms of computational time, number of iterations and number of generated columns<br />when compared with the standard CG as the size of the instances grow.</p>Read less <