The clique partitioning problem: Facets and patching facets
The clique partitioning problem (CPP) can be formulated as follows: Given is a complete graph G = (V, E), with edge weights w(ij) is an element of R for all {i, j} is an element of E. A subset A subset of or equal to E is called a clique partition if there is a partition of V into nonempty, disjoint sets V-1,..., V-k, such that each V-p (p = 1,...,k) induces a clique (i.e., a complete subgraph), and A = boolean OR (k)(p=1) {{i, ji}\i, j is an element of V-p, i # j}. The weight of such a clique partition A is defined as Sigma ({i,j}is an element ofA) w(ij). The problem is now to find a clique partition of maximum weight. The clique partitioning polytope P is the convex hull of the incidence vectors of all clique partitions of G. In this paper, we introduce several new classes of facet-defining inequalities of P. These suffice to characterize all facet-defining inequalities with right-hand side 1 or 2. Also, we present a procedure, called patching, which is able to construct new facets by making use of already-known facet-defining inequalities. A variant of this procedure is shown to run in polynomial time. Finally, we give limited empirical evidence that the facet-defining inequalities presented here can be of use in a cutting-plane approach for the clique partitioning problem. (C) 2001 John Wiley & Sons, Inc.
clique partitioning facets polyhedral combinatorics