Mostrar el registro sencillo del ítem

Column generation approaches for the software clustering problem

hal.structure.identifierUniversidade Federal Fluminense [Rio de Janeiro] [UFF]
dc.contributor.authorKRAMER, Hugo Harry
hal.structure.identifierReformulations based algorithms for Combinatorial Optimization [Realopt]
dc.contributor.authorUCHOA, Eduardo
hal.structure.identifierUniversidade Federal de Santa Maria = Federal University of Santa Maria [Santa Maria, RS, Brazil] [UFSM]
dc.contributor.authorFAMPA, Marcia
hal.structure.identifierReformulations based algorithms for Combinatorial Optimization [Realopt]
hal.structure.identifierInstitut de Mathématiques de Bordeaux [IMB]
dc.contributor.authorVANDERBECK, François
hal.structure.identifierUniversidade Federal de Santa Maria = Federal University of Santa Maria [Santa Maria, RS, Brazil] [UFSM]
dc.contributor.authorKOHLER, Viviane
dc.date.accessioned2024-04-04T03:19:19Z
dc.date.available2024-04-04T03:19:19Z
dc.date.created2015-01-15
dc.date.issued2015-12-30
dc.identifier.issn0926-6003
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/194493
dc.description.abstractEnThis 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.isoen
dc.publisherSpringer Verlag
dc.title.enColumn generation approaches for the software clustering problem
dc.typeArticle de revue
dc.identifier.doi10.1007/s10589-015-9822-9
dc.subject.halInformatique [cs]/Recherche opérationnelle [cs.RO]
bordeaux.journalComputational Optimization and Applications
bordeaux.hal.laboratoriesInstitut de Mathématiques de Bordeaux (IMB) - UMR 5251*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.peerReviewedoui
hal.identifierhal-01108161
hal.version1
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-01108161v1
bordeaux.COinSctx_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


Archivos en el ítem

ArchivosTamañoFormatoVer

No hay archivos asociados a este ítem.

Este ítem aparece en la(s) siguiente(s) colección(ones)

Mostrar el registro sencillo del ítem