Staged Column Generation Approach for the Software Clustering Problem
| hal.structure.identifier | Universidade Federal Fluminense [Rio de Janeiro] [UFF] | |
| dc.contributor.author | KRAMER, Hugo Harry | |
| hal.structure.identifier | Instituto Alberto Luiz Coimbra de Pós-Graduação e Pesquisa de Engenharia [COPPE-UFRJ] | |
| dc.contributor.author | FAMPA, Marcia | |
| hal.structure.identifier | Universidade Federal de Santa Maria = Federal University of Santa Maria [Santa Maria, RS, Brazil] [UFSM] | |
| dc.contributor.author | KÖHLER, Viviane | |
| hal.structure.identifier | Universidade Federal Fluminense [Rio de Janeiro] [UFF] | |
| dc.contributor.author | UCHOA, Eduardo | |
| hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
| dc.contributor.author | VANDERBECK, François | |
| dc.date.accessioned | 2024-04-04T02:19:47Z | |
| dc.date.available | 2024-04-04T02:19:47Z | |
| dc.date.created | 2014 | |
| dc.date.conference | 2014-02-26 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/189436 | |
| dc.description.abstractEn | <p>The present work deals with the application of a novel Column Generation (CG) approach to the<br />Software Clustering Problem (SCP). In this problem, one has a Modular Dependence Graph (MDG)<br />consisting of a set V of nodes representing the modules of a software, a set E of edges, or the set<br />of relationships between two modules u, v ∈ V of the software, and each relationship has an associated<br />weight given by c_uv . The goal is to partition the MDG in clusters, and the quality of such partition<br />must be maximized. The quality of the partition is given by a measure called Modularization Quality<br />(MQ). To tackle this problem, we apply the Dantzig-Wolfe decomposition having a formulation from<br />literature as a starting point. Given this, we present two approaches based on CG: (i) the standard<br />CG approach, and (ii) a new approach, which we call Staged Column Generation (SCG). In this new<br />approach, at each stage, the problem is solved by CG considering a restricted version of the pricing<br />subproblem. At the last stage, the complete version of the subproblem is considered and CG runs<br />until convergence. In the context of the present work, in the last stage, the subproblems are solved by<br />MIP, and in the previous stages, the restricted subproblems are solved heuristically. In addition, we<br />present a heuristic procedure to initialize the Master Problem, aiming to improve the convergence of<br />the algorithms. We test our algorithms in a set of 47 instances found in literature. With the proposed<br />approaches we were able to improve the literature results solving all these instances to optimality (45<br />of them in the root node). Furthermore, the SCG approach presented a considerable performance<br />improvement in terms of computational time, number of iterations and number of generated columns<br />when compared with the standard CG as the size of the instances grow.</p> | |
| dc.language.iso | fr | |
| dc.subject.en | Software Clustering Problem | |
| dc.subject.en | Column Generation | |
| dc.subject.en | Staged Column Generation | |
| dc.title.en | Staged Column Generation Approach for the Software Clustering Problem | |
| dc.type | Communication dans un congrès | |
| dc.subject.hal | Informatique [cs]/Recherche opérationnelle [cs.RO] | |
| 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.conference.title | ROADEF - 15ème congrès annuel de la Société française de recherche opérationnelle et d'aide à la décision | |
| bordeaux.country | FR | |
| bordeaux.conference.city | Bordeaux | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | hal-00946286 | |
| hal.version | 1 | |
| hal.invited | non | |
| hal.proceedings | non | |
| hal.conference.organizer | Société française de recherche opérationnelle et d'aide à la décision | |
| hal.conference.end | 2014-02-28 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-00946286v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.au=KRAMER,%20Hugo%20Harry&FAMPA,%20Marcia&K%C3%96HLER,%20Viviane&UCHOA,%20Eduardo&VANDERBECK,%20Fran%C3%A7ois&rft.genre=unknown |
Fichier(s) constituant ce document
| Fichiers | Taille | Format | Vue |
|---|---|---|---|
|
Il n'y a pas de fichiers associés à ce document. |
|||