This paper studies the Graph-Connected Clique-Partitioning Problem (GCCP), a\nclustering optimization model in which units are characterized by both\nindividual and relational data. This problem, introduced by Benati et al.\n(2017) under the name of Connected Partitioning Problem, shows that the\ncombination of the two data types improves the clustering quality in comparison\nwith other methodologies. Nevertheless, the resulting optimization problem is\ndifficult to solve; only small-sized instances can be solved exactly,\nlarge-sized instances require the application of heuristic algorithms. In this\npaper we improve the exact and the heuristic algorithms previously proposed.\nHere, we provide a new Integer Linear Programming (ILP) formulation, that\nsolves larger instances, but at the cost of using an exponential number of\nvariables. In order to limit the number of variables necessary to calculate the\noptimum, the new ILP formulation is solved implementing a branch-and-price\nalgorithm. The resulting pricing problem is itself a new combinatorial model:\nthe Maximum-weighted Graph-Connected Single-Clique problem (MGCSC), that we\nsolve testing various Mixed Integer Linear Programming (MILP) formulations and\nproposing a new fast "random shrink" heuristic. In this way, we are able to\nimprove the previous algorithms: The branch-and-price method outperforms the\ncomputational times of the previous MILP algorithms and the new random shrink\nheuristic, when applied to GCCP, is both faster and more accurate than the\nprevious heuristic methods. Moreover, the combination of column generation and\nrandom shrink is itself a new MILP-relaxed matheuristic that can be applied to\nlarge instances too. Its main advantage is that all heuristic local optima are\ncombined together in a restricted MILP, consisting in the application of the\nexact branch-and-price method but solving heuristically the pricing problem.\n