A large class of facets for the \(K\)-median polytope (Q543406)

The \(K\)-median problem is formulated as a minimization problem (IP) with 0-1 variables. Ignoring the integrality restrictions, one gets a linear relaxation whose polytope is not always integral. The authors develop an extended integral formulation (EP) of the original problem, with two sets of extra variables. The advantage is that an extreme point solution to (EP) is integral. This comes with a price: (EP) grows exponentially with the number of nodes. The authors proceed to project one of the sets of extra variables from the extended formulation. To this end, a result of [\textit{M. Goemans}, Notes, MIT, Cambridge (1992)] is employed. This requires a detailed study of inequalities associated to extreme directions of the projection cone. Using the reduced extended formulation, the authors establish basic properties of the facets of (IP) along the lines introduced by \textit{I. R. de Farias} [Oper. Res. Lett. 28, 161--167 (2001; Zbl 0992.90081)] and \textit{S. de Vries, M. E. Posner} and \textit{R. V. Vohra} [Math. Progr. 110, No. 2 (A), 261--285 (2007; Zbl 1130.90058)]. Inequalities introduced in this paper are facet-defining under weaker conditions than the published ones and compares favorably with their predecessors. The paper also contains a heuristic method that uses the new restrictions to separate a fractional extreme point from the integer hull of the polytope of (IP).