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.
Type de document :
Article dans une revue
Computational Optimization and Applications, Springer Verlag, 2015, 〈http://link.springer.com/article/10.1007/s10589-015-9822-9〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01108161
Contributeur : François Vanderbeck <>
Soumis le : jeudi 22 janvier 2015 - 11:48:19
Dernière modification le : jeudi 11 janvier 2018 - 06:22:12

Identifiants

  • HAL Id : hal-01108161, version 1

Collections

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〉. 〈hal-01108161〉

Partager

Métriques

Consultations de la notice

293