ON THE p-MEDIAN POLYTOPE

The p-Median problem defined on a complete directed graph with n nodes (K + (Combining right arrow above sign)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(K + (Combining right arrow above sign)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 V of cardinality p and entering in every node of V \ P. In this paper we show that the polytope Mn-p(K + (Combining right arrow above sign)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∈X xi = n - p). This allows us to define a very general class of facet-defining valid inequalities of Mn-p(K + (Combining right arrow above sign)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 K + (Combining right arrow above sign)n (V, A). We also define a very basic class of facet-defining inequalities of Mn-p(K + (Combining right arrow above sign)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(K + (Combining right arrow above sign)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 + (Combining right arrow above sign)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.