New facets of the clique partitioning polytope

The clique partitioning problem is a combinatorial optimisation problem which has many applications. At present, the most promising exact algorithms are those that are based on an understanding of the associated polytope. We present two new families of valid inequalities for that polytope, and show that the inequalities define facets under certain conditions.