Column generation approaches for the software clustering problem
| hal.structure.identifier | Universidade Federal Fluminense [Rio de Janeiro] [UFF] | |
| dc.contributor.author | KRAMER, Hugo Harry | |
| hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
| dc.contributor.author | UCHOA, Eduardo | |
| hal.structure.identifier | Universidade Federal de Santa Maria = Federal University of Santa Maria [Santa Maria, RS, Brazil] [UFSM] | |
| dc.contributor.author | FAMPA, Marcia | |
| hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
| hal.structure.identifier | Institut de Mathématiques de Bordeaux [IMB] | |
| dc.contributor.author | VANDERBECK, François | |
| hal.structure.identifier | Universidade Federal de Santa Maria = Federal University of Santa Maria [Santa Maria, RS, Brazil] [UFSM] | |
| dc.contributor.author | KOHLER, Viviane | |
| dc.date.accessioned | 2024-04-04T03:19:19Z | |
| dc.date.available | 2024-04-04T03:19:19Z | |
| dc.date.created | 2015-01-15 | |
| dc.date.issued | 2015-12-30 | |
| dc.identifier.issn | 0926-6003 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/194493 | |
| dc.description.abstractEn | 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. | |
| dc.language.iso | en | |
| dc.publisher | Springer Verlag | |
| dc.title.en | Column generation approaches for the software clustering problem | |
| dc.type | Article de revue | |
| dc.identifier.doi | 10.1007/s10589-015-9822-9 | |
| dc.subject.hal | Informatique [cs]/Recherche opérationnelle [cs.RO] | |
| bordeaux.journal | Computational Optimization and Applications | |
| bordeaux.hal.laboratories | Institut de Mathématiques de Bordeaux (IMB) - UMR 5251 | * |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | hal-01108161 | |
| hal.version | 1 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-01108161v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=Computational%20Optimization%20and%20Applications&rft.date=2015-12-30&rft.eissn=0926-6003&rft.issn=0926-6003&rft.au=KRAMER,%20Hugo%20Harry&UCHOA,%20Eduardo&FAMPA,%20Marcia&VANDERBECK,%20Fran%C3%A7ois&KOHLER,%20Viviane&rft.genre=article |
Fichier(s) constituant ce document
| Fichiers | Taille | Format | Vue |
|---|---|---|---|
|
Il n'y a pas de fichiers associés à ce document. |
|||