IDEAS home Printed from https://ideas.repec.org/a/spr/coopap/v55y2013i1p113-135.html
   My bibliography  Save this article

Mixed-Integer Linear Programming Formulations for the Software Clustering Problem

Author

Listed:
  • Viviane Köhler
  • Marcia Fampa
  • Olinto Araújo

Abstract

The clustering problem has an important application in software engineering, which usually deals with large software systems with complex structures. To facilitate the work of software maintainers, components of the system are divided into groups in such a way that the groups formed contain highly-interdependent modules and the independent modules are placed in different groups. The measure used to analyze the quality of the system partition is called Modularization Quality (MQ). Designers represent the software system as a graph where modules are represented by nodes and relationships between modules are represented by edges. This graph is referred in the literature as Module Dependency Graph (MDG). The Software Clustering Problem (SCP) consists in finding the partition of the MDG that maximizes the MQ. In this paper we present three new mathematical programming formulations for the SCP. Firstly, we formulate the SCP as a sum of linear fractional functions problem and then we apply two different linearization procedures to reformulate the problem as Mixed-Integer Linear Programming (MILP) problems. We discuss a preprocessing technique that reduces the size of the original problem and develop valid inequalities that have been shown to be very effective in tightening the formulations. We present numerical results that compare the formulations proposed and compare our results with the solutions obtained by the exhaustive algorithm supported by the freely available Bunch clustering tool, for benchmark problems. Copyright Springer Science+Business Media New York 2013

Suggested Citation

  • Viviane Köhler & Marcia Fampa & Olinto Araújo, 2013. "Mixed-Integer Linear Programming Formulations for the Software Clustering Problem," Computational Optimization and Applications, Springer, vol. 55(1), pages 113-135, May.
    • Handle: RePEc:spr:coopap:v:55:y:2013:i:1:p:113-135
    DOI: 10.1007/s10589-012-9512-9
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10589-012-9512-9
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10589-012-9512-9?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Li, Han-Lin, 1994. "A global approach for general 0-1 fractional programming," European Journal of Operational Research, Elsevier, vol. 73(3), pages 590-596, March.
    2. Danny Z. Chen & Ovidiu Daescu & Yang Dai & Naoki Katoh & Xiaodong Wu & Jinhui Xu, 2005. "Efficient Algorithms and Implementations for Optimizing the Sum of Linear Fractional Functions, with Applications," Journal of Combinatorial Optimization, Springer, vol. 9(1), pages 69-90, February.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Lifeng Mu & Vijayan Sugumaran & Fangyuan Wang, 2020. "A Hybrid Genetic Algorithm for Software Architecture Re-Modularization," Information Systems Frontiers, Springer, vol. 22(5), pages 1133-1161, October.
    2. Lifeng Mu & Vijayan Sugumaran & Fangyuan Wang, 0. "A Hybrid Genetic Algorithm for Software Architecture Re-Modularization," Information Systems Frontiers, Springer, vol. 0, pages 1-29.
    3. Hugo Harry Kramer & Eduardo Uchoa & Marcia Fampa & Viviane Köhler & François Vanderbeck, 2016. "Column generation approaches for the software clustering problem," Computational Optimization and Applications, Springer, vol. 64(3), pages 843-864, July.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Chang, Ching-Ter, 2001. "On the polynomial mixed 0-1 fractional programming problems," European Journal of Operational Research, Elsevier, vol. 131(1), pages 224-227, May.
    2. Polyakovskiy, S. & Neumann, F., 2017. "The Packing While Traveling Problem," European Journal of Operational Research, Elsevier, vol. 258(2), pages 424-439.
    3. Billionnet, Alain, 2004. "Mixed integer programming for the 0-1 maximum probability model," European Journal of Operational Research, Elsevier, vol. 156(1), pages 83-91, July.
    4. Wu, Tai-Hsi, 1997. "A note on a global approach for general 0-1 fractional programming," European Journal of Operational Research, Elsevier, vol. 101(1), pages 220-223, August.
    5. Panagiotis Kontogiorgos & Nikolaos Chrysanthopoulos & George P. Papavassilopoulos, 2018. "A Mixed-Integer Programming Model for Assessing Energy-Saving Investments in Domestic Buildings under Uncertainty," Energies, MDPI, vol. 11(4), pages 1-14, April.
    6. Jose Joaquin del Pozo-Antúnez & Francisco Fernández-Navarro & Horacio Molina-Sánchez & Antonio Ariza-Montes & Mariano Carbonero-Ruz, 2021. "The Machine-Part Cell Formation Problem with Non-Binary Values: A MILP Model and a Case of Study in the Accounting Profession," Mathematics, MDPI, vol. 9(15), pages 1-16, July.
    7. Li, Han-Lin & Chang, Ching-Ter, 1998. "An approximate approach of global optimization for polynomial programming problems," European Journal of Operational Research, Elsevier, vol. 107(3), pages 625-632, June.
    8. Juan S. Borrero & Colin Gillen & Oleg A. Prokopyev, 2017. "Fractional 0–1 programming: applications and algorithms," Journal of Global Optimization, Springer, vol. 69(1), pages 255-282, September.
    9. Hua, Guowei & Cheng, T.C.E. & Wang, Shouyang, 2011. "The maximum capture per unit cost location problem," International Journal of Production Economics, Elsevier, vol. 131(2), pages 568-574, June.
    10. Chang, Ching-Ter, 2002. "On the posynomial fractional programming problems," European Journal of Operational Research, Elsevier, vol. 143(1), pages 42-52, November.
    11. Takahito Kuno & Toshiyuki Masaki, 2013. "A practical but rigorous approach to sum-of-ratios optimization in geometric applications," Computational Optimization and Applications, Springer, vol. 54(1), pages 93-109, January.
    12. T Drezner & Z Drezner & P Kalczynski, 2011. "A cover-based competitive location model," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(1), pages 100-113, January.
    13. Strauss, Arne K. & Klein, Robert & Steinhardt, Claudius, 2018. "A review of choice-based revenue management: Theory and methods," European Journal of Operational Research, Elsevier, vol. 271(2), pages 375-387.
    14. Chang, Ching-Ter, 2006. "Formulating the mixed integer fractional posynomial programming," European Journal of Operational Research, Elsevier, vol. 173(2), pages 370-386, September.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:coopap:v:55:y:2013:i:1:p:113-135. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.