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.

ON THE p-MEDIAN POLYTOPE

AVELLA P;
2001

Abstract

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.
File in questo prodotto:
File Dimensione Formato  
MP_2001.pdf

non disponibili

Licenza: Non specificato
Dimensione 138.4 kB
Formato Adobe PDF
138.4 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/20.500.12070/2340
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 45
  • ???jsp.display-item.citation.isi??? ND
social impact