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 inve stigate 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. Through out the paper, a block diagonal matrix is regarded as the adjacency ma trix of a disjoint union of complete bipartite graphs. The presentatio n and the derivation of the results heavily rely on this graph-theoret ic interpretation. (C) 1997 John Wiley & Sons, Inc.