Staged Column Generation Approach for the Software Clustering Problem

International audienceThe present work deals with the application of a novel Column Generation (CG) approach to theSoftware Clustering Problem (SCP). In this problem, one has a Modular Dependence Graph (MDG)consisting of a set V of nodes representing the modules of a software, a set E of edges, or the setof relationships between two modules u, v ∈ V of the software, and each relationship has an associatedweight given by c_uv . The goal is to partition the MDG in clusters, and the quality of such partitionmust be maximized. The quality of the partition is given by a measure called Modularization Quality(MQ). To tackle this problem, we apply the Dantzig-Wolfe decomposition having a formulation fromliterature as a starting point. Given this, we present two approaches based on CG: (i) the standardCG approach, and (ii) a new approach, which we call Staged Column Generation (SCG). In this newapproach, at each stage, the problem is solved by CG considering a restricted version of the pricingsubproblem. At the last stage, the complete version of the subproblem is considered and CG runsuntil convergence. In the context of the present work, in the last stage, the subproblems are solved byMIP, and in the previous stages, the restricted subproblems are solved heuristically. In addition, wepresent a heuristic procedure to initialize the Master Problem, aiming to improve the convergence ofthe algorithms. We test our algorithms in a set of 47 instances found in literature. With the proposedapproaches we were able to improve the literature results solving all these instances to optimality (45of them in the root node). Furthermore, the SCG approach presented a considerable performanceimprovement in terms of computational time, number of iterations and number of generated columnswhen compared with the standard CG as the size of the instances grow.