A large class of facets for the K-median polytope

The polyhedral structure of the K-median problem is examined. We present an extended formulation that is integral but grows exponentially with the number of nodes. Then, some extra variables are projected out. Based on the reduced formulation, we develop two basic properties for facets of K-median problem. By applying the two properties, we generalize two known classes of facets, de Vries facets and de Farias facets. The computational study illustrates that the generalization is significant.