IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v297y2022i3p817-830.html
   My bibliography  Save this article

A branch-and-price procedure for clustering data that are graph connected

Author

Listed:
  • Benati, Stefano
  • Ponce, Diego
  • Puerto, Justo
  • Rodríguez-Chía, Antonio M.

Abstract

This paper studies the Graph-Connected Clique-Partitioning Problem (GCCP), a clustering optimization model in which units are characterized by both individual and relational data. This problem, introduced by Benati, Puerto, and Rodríguez-Chía (2017) under the name of Connected Partitioning Problem, shows that the combination of the two data types improves the clustering quality in comparison with other methodologies. Nevertheless, the resulting optimization problem is difficult to solve; only small-sized instances can be solved exactly, large-sized instances require the application of heuristic algorithms. In this paper we improve the exact and the heuristic algorithms previously proposed. Here, we provide a new Integer Linear Programming (ILP) formulation, that solves larger instances, but at the cost of using an exponential number of variables. In order to limit the number of variables necessary to calculate the optimum, the new ILP formulation is solved implementing a branch-and-price (B&P) algorithm. The resulting pricing problem is itself a new combinatorial model: the Maximum-weighted Graph-Connected Single-Clique problem (MGCSC), that we solve testing various Mixed Integer Linear Programming (MILP) formulations and proposing a new fast “random shrink” heuristic. In this way, we are able to improve the previous algorithms: The B&P method outperforms the computational times of the previous MILP algorithms and the new random shrink heuristic, when applied to GCCP, is both faster and more accurate than the previous heuristic methods. Moreover, the combination of column generation and random shrink is itself a new MILP-relaxed matheuristic that can be applied to large instances too. Its main advantage is that all heuristic local optima are combined together in a restricted MILP, consisting in the application of the exact B&P method but solving heuristically the pricing problem.

Suggested Citation

  • Benati, Stefano & Ponce, Diego & Puerto, Justo & Rodríguez-Chía, Antonio M., 2022. "A branch-and-price procedure for clustering data that are graph connected," European Journal of Operational Research, Elsevier, vol. 297(3), pages 817-830.
    • Handle: RePEc:eee:ejores:v:297:y:2022:i:3:p:817-830
    DOI: 10.1016/j.ejor.2021.05.043
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221721004719
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2021.05.043?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. Raidl, Günther R., 2015. "Decomposition based hybrid metaheuristics," European Journal of Operational Research, Elsevier, vol. 244(1), pages 66-76.
    2. Sato, Keisuke & Fukumura, Naoto, 2012. "Real-time freight locomotive rescheduling and uncovered train detection during disruption," European Journal of Operational Research, Elsevier, vol. 221(3), pages 636-648.
    3. Benati, Stefano & Puerto, Justo & Rodríguez-Chía, Antonio M., 2017. "Clustering data that are graph connected," European Journal of Operational Research, Elsevier, vol. 261(1), pages 43-53.
    4. Samuel Deleplanque & Martine Labbé & Diego Ponce & Justo Puerto, 2020. "A Branch-Price-and-Cut Procedure for the Discrete Ordered Median Problem," INFORMS Journal on Computing, INFORMS, vol. 32(3), pages 582-599, July.
    5. Laporte, Gilbert, 1992. "The traveling salesman problem: An overview of exact and approximate algorithms," European Journal of Operational Research, Elsevier, vol. 59(2), pages 231-247, June.
    6. Stefano Gualandi & Federico Malucelli, 2013. "Constraint Programming-based Column Generation," Annals of Operations Research, Springer, vol. 204(1), pages 11-32, April.
    7. Bektaş, Tolga & Gouveia, Luis, 2014. "Requiem for the Miller–Tucker–Zemlin subtour elimination constraints?," European Journal of Operational Research, Elsevier, vol. 236(3), pages 820-832.
    8. Marco E. Lübbecke & Jacques Desrosiers, 2005. "Selected Topics in Column Generation," Operations Research, INFORMS, vol. 53(6), pages 1007-1023, December.
    9. Egon Balas & Vašek Chvátal & Jaroslav Nešetřil, 1987. "On the Maximum Weight Clique Problem," Mathematics of Operations Research, INFORMS, vol. 12(3), pages 522-535, August.
    10. Jacques Desrosiers & Marco E. Lübbecke, 2005. "A Primer in Column Generation," Springer Books, in: Guy Desaulniers & Jacques Desrosiers & Marius M. Solomon (ed.), Column Generation, chapter 0, pages 1-32, Springer.
    11. Bothorel, Cecile & Cruz, Juan David & Magnani, Matteo & Micenková, Barbora, 2015. "Clustering attributed graphs: Models, measures and methods," Network Science, Cambridge University Press, vol. 3(3), pages 408-444, September.
    12. Gambella, Claudio & Ghaddar, Bissan & Naoum-Sawaya, Joe, 2021. "Optimization problems for machine learning: A survey," European Journal of Operational Research, Elsevier, vol. 290(3), pages 807-828.
    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. Calvino, José J. & López-Haro, Miguel & Muñoz-Ocaña, Juan M. & Puerto, Justo & Rodríguez-Chía, Antonio M., 2022. "Segmentation of scanning-transmission electron microscopy images using the ordered median problem," European Journal of Operational Research, Elsevier, vol. 302(2), pages 671-687.
    2. Healy, Patrick & Jozefowiez, Nicolas & Laroche, Pierre & Marchetti, Franc & Martin, Sébastien & Róka, Zsuzsanna, 2024. "A branch-and-cut algorithm for the connected max-k-cut problem," European Journal of Operational Research, Elsevier, vol. 312(1), pages 117-124.
    3. Ponce, Diego & Puerto, Justo & Temprano, Francisco, 2024. "Mixed-integer linear programming formulations and column generation algorithms for the Minimum Normalized Cuts problem on networks," European Journal of Operational Research, Elsevier, vol. 316(2), pages 519-538.
    4. Blanco, Víctor & Gázquez, Ricardo & Ponce, Diego & Puerto, Justo, 2023. "A branch-and-price approach for the continuous multifacility monotone ordered median problem," European Journal of Operational Research, Elsevier, vol. 306(1), pages 105-126.

    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. Ponce, Diego & Puerto, Justo & Temprano, Francisco, 2024. "Mixed-integer linear programming formulations and column generation algorithms for the Minimum Normalized Cuts problem on networks," European Journal of Operational Research, Elsevier, vol. 316(2), pages 519-538.
    2. Benati, Stefano & Puerto, Justo & Rodríguez-Chía, Antonio M., 2017. "Clustering data that are graph connected," European Journal of Operational Research, Elsevier, vol. 261(1), pages 43-53.
    3. Blanco, Víctor & Gázquez, Ricardo & Ponce, Diego & Puerto, Justo, 2023. "A branch-and-price approach for the continuous multifacility monotone ordered median problem," European Journal of Operational Research, Elsevier, vol. 306(1), pages 105-126.
    4. Calvino, José J. & López-Haro, Miguel & Muñoz-Ocaña, Juan M. & Puerto, Justo & Rodríguez-Chía, Antonio M., 2022. "Segmentation of scanning-transmission electron microscopy images using the ordered median problem," European Journal of Operational Research, Elsevier, vol. 302(2), pages 671-687.
    5. Duygu Pamukcu & Burcu Balcik, 2020. "A multi-cover routing problem for planning rapid needs assessment under different information-sharing settings," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 42(1), pages 1-42, March.
    6. Víctor M. Albornoz & Gabriel E. Zamora, 2021. "Decomposition-based heuristic for the zoning and crop planning problem with adjacency constraints," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 29(1), pages 248-265, April.
    7. Ferrarini, Luca & Gualandi, Stefano, 2022. "Total Coloring and Total Matching: Polyhedra and Facets," European Journal of Operational Research, Elsevier, vol. 303(1), pages 129-142.
    8. Thomas, Anu & Venkateswaran, Jayendran & Singh, Gaurav & Krishnamoorthy, Mohan, 2014. "A resource constrained scheduling problem with multiple independent producers and a single linking constraint: A coal supply chain example," European Journal of Operational Research, Elsevier, vol. 236(3), pages 946-956.
    9. Mariana Escallón-Barrios & Daniel Castillo-Gomez & Jorge Leal & Carlos Montenegro & Andrés L. Medaglia, 2022. "Improving harvesting operations in an oil palm plantation," Annals of Operations Research, Springer, vol. 314(2), pages 411-449, July.
    10. Breugem, T. & van Rossum, B.T.C. & Dollevoet, T. & Huisman, D., 2022. "A column generation approach for the integrated crew re-planning problem," Omega, Elsevier, vol. 107(C).
    11. Breugem, T. & Dollevoet, T.A.B. & Huisman, D., 2019. "A Column Generation Approach for the Integrated Crew Re-Planning Problem," Econometric Institute Research Papers EI2019-31, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    12. Luisa I. Martínez-Merino & Diego Ponce & Justo Puerto, 2023. "Constraint relaxation for the discrete ordered median problem," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 31(3), pages 538-561, October.
    13. Christensen, Tue R.L. & Labbé, Martine, 2015. "A branch-cut-and-price algorithm for the piecewise linear transportation problem," European Journal of Operational Research, Elsevier, vol. 245(3), pages 645-655.
    14. Ogbe, Emmanuel & Li, Xiang, 2017. "A new cross decomposition method for stochastic mixed-integer linear programming," European Journal of Operational Research, Elsevier, vol. 256(2), pages 487-499.
    15. François Clautiaux & Cláudio Alves & José Valério de Carvalho & Jürgen Rietz, 2011. "New Stabilization Procedures for the Cutting Stock Problem," INFORMS Journal on Computing, INFORMS, vol. 23(4), pages 530-545, November.
    16. Brech, Claus-Henning & Ernst, Andreas & Kolisch, Rainer, 2019. "Scheduling medical residents’ training at university hospitals," European Journal of Operational Research, Elsevier, vol. 274(1), pages 253-266.
    17. de Lima, Vinícius L. & Alves, Cláudio & Clautiaux, François & Iori, Manuel & Valério de Carvalho, José M., 2022. "Arc flow formulations based on dynamic programming: Theoretical foundations and applications," European Journal of Operational Research, Elsevier, vol. 296(1), pages 3-21.
    18. Omid Shahvari & Rasaratnam Logendran & Madjid Tavana, 2022. "An efficient model-based branch-and-price algorithm for unrelated-parallel machine batching and scheduling problems," Journal of Scheduling, Springer, vol. 25(5), pages 589-621, October.
    19. Ghazale Kordi & Parsa Hasanzadeh-Moghimi & Mohammad Mahdi Paydar & Ebrahim Asadi-Gangraj, 2023. "A multi-objective location-routing model for dental waste considering environmental factors," Annals of Operations Research, Springer, vol. 328(1), pages 755-792, September.
    20. Ann-Kathrin Rothenbächer & Michael Drexl & Stefan Irnich, 2018. "Branch-and-Price-and-Cut for the Truck-and-Trailer Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 52(5), pages 1174-1190, October.

    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:eee:ejores:v:297:y:2022:i:3:p:817-830. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.