The polytope of block diagonal matrices and complete bipartite partitionings

Motivated by a fundamental clustering problem arising in several areas (production management, marketing, numerical analysis, etc.), we investigate the facial structure of the polytope whose extreme points are all 0–1 block diagonal matrices. For this polytope, general properties of facet-defining inequalities are investigated and specific families of facets are identified. Various techniques for lifting or combining facet-defining inequalities into new ones are also presented. Throughout the paper, a block diagonal matrix is regarded as the adjacency matrix of a disjoint union of complete bipartite graphs. The presentation and the derivation of the results heavily rely on this graph-theoretic interpretation.