Document Type : Original Article
Authors
University of Guilan
Abstract
Standard semidefinite programming (SDP) relaxations for the Minimum Sum-of-Squares Clustering problem often produce weak lower bounds. We tighten the relaxation by adding transitivity constraints that enforce the equivalence-relation structure of cluster assignments: if points i and j are together, and i and k are together, then j and k must be together as well. We prove that these constraints are valid inequalities for the original problem, and that the new relaxation dominates the standard one in bound quality. Numerical experiments on Ruspini, Iris, Wine, and synthetic datasets show that our model consistently outperforms both the standard SDP relaxation and a recent MILP formulation, with improvements reaching up to 49% on synthetic instances and over 20% on Wine. The gains are largest when clusters overlap or when the number of clusters or data size grows. This comes at a higher computational cost due to the O(n^3 ) additional constraints, but the trade-off is acceptable for moderate-scale problems. The proposed relaxation offers a practical way to strengthen SDP-based clustering by encoding logical assignment consistency directly within the convex framework.
Keywords
)