KRAMER, Hugo Harry; UCHOA, Eduardo; FAMPA, Marcia; VANDERBECK, François; KOHLER, Viviane

doi:10.1007/s10589-015-9822-9

Métadonnées

Afficher la notice complète

Licence d’utilisation du document

KRAMER, Hugo Harry
Universidade Federal Fluminense [Rio de Janeiro] [UFF]

UCHOA, Eduardo
Reformulations based algorithms for Combinatorial Optimization [Realopt]

FAMPA, Marcia
Universidade Federal de Santa Maria = Federal University of Santa Maria [Santa Maria, RS, Brazil] [UFSM]

Langue

Article de revue

Ce document a été publié dans

Computational Optimization and Applications. 2015-12-30

Springer Verlag

Résumé en anglais

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.< Réduire

Métadonnées

Partager cette publication !

Licence d’utilisation du document

Column generation approaches for the software clustering problem

Langue

Ce document a été publié dans

Résumé en anglais

URI

DOI

Origine

Unités de recherche