Column generation approaches for the software clustering problem

Abstract : This work presents the application of branch-and-price approaches to the auto- matic version of the Software Clustering Problem. To tackle this problem, we apply the Dantzig-Wolfe decomposition to a formulation from literature. Given this, we present two Column Generation (CG) approaches to solve the linear programming relaxation of the resulting reformulation: the standard CG approach, and a new approach, which we call Staged Column Generation (SCG). Also, we propose a modification to the pricing subproblem that allows to add multiple columns at each iteration of the CG. We test our algorithms in a set of 45 instances from the literature. The proposed approaches were able to improve the literature results solving all these instances to optimality. Furthermore, the SCG approach presented a considerable performance improvement regarding computational time, number of iterations and generated columns when compared with the standard CG as the size of the instances grows.
Document type :
Journal articles
Complete list of metadatas

https://hal.inria.fr/hal-01108161
Contributor : François Vanderbeck <>
Submitted on : Thursday, January 22, 2015 - 11:48:19 AM
Last modification on : Friday, June 14, 2019 - 12:56:08 PM

Identifiers

Citation

Hugo Harry Kramer, Eduardo Uchoa, Marcia Fampa, François Vanderbeck, Viviane Kohler. Column generation approaches for the software clustering problem. Computational Optimization and Applications, Springer Verlag, 2015, ⟨http://link.springer.com/article/10.1007/s10589-015-9822-9⟩. ⟨10.1007/s10589-015-9822-9⟩. ⟨hal-01108161⟩

Share

Metrics

Record views

404