Branch-and-price-and-cut on the clique partitioning problem with minimum clique size requirement

Given a complete graph Kn=(V,E)Kn=(V,E) with edge weight cece on each edge, we consider the problem of partitioning the vertices of graph KnKn into subcliques that have at least SS vertices, so as to minimize the total weight of the edges that have both endpoints in the same subclique. In this paper, we consider using the branch-and-price method to solve the problem. We demonstrate the necessity of cutting planes for this problem and suggest effective ways of adding cutting planes in the branch-and-price framework. The NP hard pricing problem is solved as an integer programming problem. We present computational results on large randomly generated problems.