The p-Median problem defined on a complete directed graph with n nodes (&Krarr;n(V, A)) asks for a subset T ⊆ V of cardinality p and such that the weight of n – p arcs going from T to every node of V \ T, is minimized. The p-Median polytope Mn−p(&Krarr;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 ⊆ V of cardinality p and entering in every node of V \ P. In this paper we show that the polytope Mn−p(&Krarr;n(V, A)) is an ‘integral slice’ of the Stable Set polytope STAB(Gn) associated with a suitable graph Gn(X, J) (i.e. is the convex hull of the integral points in the intersection of STAB(Gn) with the hyperplane Σi∈Xxi = n – p). This allows us to define a very general class of facet-defining valid inequalities of Mn−p(&Krarr;n(V, A)), called W-2 inequalities, which are also facet-defining for STAB(Gn) and have a very compact representation in terms of suitable subgraphs of &Krarr;n(V, A)). We also define a very basic class of facet-defining inequalities of Mn−p(&Krarr;n(V, A)), called Cover inequalities, which are not valid for STAB(Gn). The importance and the role of the above classes is testified by the observation that they provide the complete description of Mn−p(&Krarr;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(&Krarr;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.
