RT journal article
T1 A Branch-and-price procedure for clustering data that are graph connected (versión aceptada)
A1 Benati, Stefan
A1 Ponce, Diego
A1 Puerto, Justo
A1 Rodríguez Chía, Antonio Manuel
A2 Estadística e Investigación Operativa
K1 Combinatorial optimization
K1 Clustering Mixed
K1 Mixed integer programming
K1 Branch-and-price
AB This paper studies the Graph-Connected Clique-Partitioning Problem (GCCP), a clustering optimizationmodel in which units are characterized by both individual and relational data. This problem, introducedby Benati, Puerto, and Rodríguez-Chía (2017) under the name of Connected Partitioning Problem, showsthat the combination of the two data types improves the clustering quality in comparison with othermethodologies. Nevertheless, the resulting optimization problem is difficult to solve; only small-sizedinstances can be solved exactly, large-sized instances require the application of heuristic algorithms. Inthis paper we improve the exact and the heuristic algorithms previously proposed. Here, we provide anew Integer Linear Programming (ILP) formulation, that solves larger instances, but at the cost of usingan exponential number of variables. In order to limit the number of variables necessary to calculatethe optimum, the new ILP formulation is solved implementing a branch-and-price (B&P) algorithm. Theresulting pricing problem is itself a new combinatorial model: the Maximum-weighted Graph-ConnectedSingle-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 improvethe previous algorithms: The B&P method outperforms the computational times of the previous MILPalgorithms and the new random shrink heuristic, when applied to GCCP, is both faster and more accuratethan the previous heuristic methods. Moreover, the combination of column generation and random shrinkis itself a new MILP-relaxed matheuristic that can be applied to large instances too. Its main advantageis that all heuristic local optima are combined together in a restricted MILP, consisting in the applicationof the exact B&P method but solving heuristically the pricing problem
SN 1872-6860
YR 2022
FD 2022
LK http://hdl.handle.net/10498/38453
UL http://hdl.handle.net/10498/38453
LA eng
DS Repositorio Institucional de la Universidad de Cádiz
RD 08-nov-2026