Show simple item record

dc.contributor.authorBenati, Stefano
dc.contributor.authorPonce, Diego
dc.contributor.authorPuerto, Justo
dc.contributor.authorRodríguez Chía, Antonio Manuel 
dc.date.accessioned2026-01-23T13:32:06Z
dc.date.available2026-01-23T13:32:06Z
dc.date.issued2022
dc.identifier.issn1872-6860
dc.identifier.issn0377-2217
dc.identifier.urihttp://hdl.handle.net/10498/38446
dc.description.abstractThis 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.es_ES
dc.formatapplication/pdfes_ES
dc.language.isoenges_ES
dc.publisherElsevieres_ES
dc.rightsAttribution-NonCommercial-NoDerivatives 4.0 Internacional*
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0/*
dc.sourceEuropean Journal of Operational Research - 2022, Vol. 297 n.3 pp. 817-830es_ES
dc.subjectCombinatorial optimizationes_ES
dc.subjectClusteringes_ES
dc.subjectMixed integer programminges_ES
dc.subjectBranch-and-pricees_ES
dc.titleA Branch-and-price procedure for clustering data that are graph connectedes_ES
dc.typejournal articlees_ES
dc.rights.accessRightsclosed accesses_ES
dc.identifier.doi/10.1016/j.ejor.2021.05.043
dc.type.hasVersionVoRes_ES


Files in this item

This item appears in the following Collection(s)

Show simple item record

Attribution-NonCommercial-NoDerivatives 4.0 Internacional
This work is under a Creative Commons License Attribution-NonCommercial-NoDerivatives 4.0 Internacional