Cliques and clustering: A combinatorial approach

We use column generation and a specialized branching technique for solving constrained clustering problems. We also develop and implement an innovative combinatorial method for solving the pricing subproblems. Computational experiments comparing the resulting branch-and-price method to competing methodologies in the literature are presented and suggest that our technique yields a significant improvement on the hard instances of this problem.