Column generation approaches for the software clustering problem

Hugo Harry Kramer (), Eduardo Uchoa (), Marcia Fampa (), Viviane Köhler () and François Vanderbeck ()
Additional contact information
Hugo Harry Kramer: Universidade Federal Fluminense
Eduardo Uchoa: Universidade Federal Fluminense
Marcia Fampa: Universidade Federal do Rio de Janeiro
Viviane Köhler: Universidade Federal de Santa Maria
François Vanderbeck: Université de Bordeaux & Inria Bordeaux Sud-Ouest

Computational Optimization and Applications, 2016, vol. 64, issue 3, No 9, 843-864

Abstract: Abstract This work presents the application of branch-and-price approaches to the automatic version of the Software Clustering Problem. To tackle this problem, we apply the Dantzig–Wolfe decomposition to a formulation from the 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.

Keywords: Software Clustering Problem; Column Generation; Branch-and-Price (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10589-015-9822-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:coopap:v:64:y:2016:i:3:d:10.1007_s10589-015-9822-9

Ordering information: This journal article can be ordered from
http://www.springer.com/math/journal/10589

DOI: 10.1007/s10589-015-9822-9

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().