On the p-Median polytope

The p-Median problem defined on a complete directed graph with n nodes ((K) over right arrow (n)(V, A)) asks for a subset T subset of or equal to V of cardinality p and such that the weight of n - p arcs going from T to every node of V \ I, is minimized. The p-Median polytope Mn-p((K) over right arrow (n)(V, A)) is the convex hull of the incidence Vectors of all the subsets of n - p arcs in A leaving a set T subset of or equal to V of cardinality p and entering in every node of V \ P. In this paper we show that the polytope Mn-p((K) over right arrow (n)(V, A)) is an "integral slice" of the Stable Set polytope STAB(G(n)) associated with a suitable graph G(n)(X, J) (i.e. is the convex hull of the integral points in the intersection of STAB(G(n)) with the hyperplane Sigma (i is an element ofX) x(i) = n - p) This allows us to define a very general class of facet-defining valid inequalities of Mn-p((K) over right arrow (n)(V, A)), called W-2 inequalities, which are also facet defining for STAB(G(n)) and have a very compact representation in terms of suitable subgraphs of (K) over right arrow (n)(V, A). We also define a very basic class of facet-defining inequalities of Mn-p((K) over right arrow (n)(V, A)), called Cover inequalities, which are not valid for STAB(G(n)). The importance and the role of the above classes is testified by the observation that they provide the complete description of Mn-p((K) over right arrow (n)(V, A)) if p = n - 2. Cover inequalities can be strengthened by exploiting optimality. We introduce a new class of inequalities, called I*-Cover inequalities, which have a non-standard nature: they are not valid for Mn-p((K) over right arrow (n)(V, A)), but do not cut-off the optimal solution. A preliminary computational experience shows that the inequalities introduced in this paper are very effective in the solution of test instances.