Program > By author > Uchoa Eduardo

The present work deals with the application of a novel Column Generation (CG) approach to the
Software 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 set
of relationships between two modules u, v ∈ V of the software, and each relationship has an associated
weight given by c_uv . The goal is to partition the MDG in clusters, and the quality of such partition
must 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 from
literature as a starting point. Given this, we present two approaches based on CG: (i) the standard
CG approach, and (ii) a new approach, which we call Staged Column Generation (SCG). In this new
approach, at each stage, the problem is solved by CG considering a restricted version of the pricing
subproblem. At the last stage, the complete version of the subproblem is considered and CG runs
until convergence. In the context of the present work, in the last stage, the subproblems are solved by
MIP, and in the previous stages, the restricted subproblems are solved heuristically. In addition, we
present a heuristic procedure to initialize the Master Problem, aiming to improve the convergence of
the algorithms. We test our algorithms in a set of 47 instances found in literature. With the proposed
approaches we were able to improve the literature results solving all these instances to optimality (45
of them in the root node). Furthermore, the SCG approach presented a considerable performance
improvement in terms of computational time, number of iterations and number of generated columns
when compared with the standard CG as the size of the instances grow.