On the p-Median polytope
On the p-Median polytope
复制标题
关于 p 中位数多胞形
DOI：
10.1007/pl00011405
复制
发表时间：
2001
影响因子：
2.7
通讯作者：
A. Sassano
中科院分区：
文献类型：
--
作者：
P. Avella;A. Sassano
定义在一个有n个节点的完全有向图（$\vec{K}$n（V，A））上的p-中值问题要求基数为p的子集T <$V，使得从T到V <$T的每个节点的n-p条弧的权重最小化。p-中值多胞形Mn-p（$\vec{K}$n（V，A））是A中所有n-p弧的子集的关联向量的船体，它离开基数为p的集合T <$V并进入V <$P的每个节点。本文证明了多胞形Mn-p（$\vec{K}$n（V，A））是与合适的图Gn（X，J）（即是STAB（Gn）与超平面∑i∈Xxi=n-p的交点的积分点的凸船体）。这使得我们可以定义Mn-p的一类非常一般的定义面的有效不等式（$\vec{K}$n（V，A）），称为W-2不等式，它们也是STAB（Gn）的面定义不等式，并且用$\vec{K}$n（V，A）的适当子图表示，具有非常紧凑的表示。我们还定义了Mn-p的一类非常基本的面定义不等式（$\vec{K}$n（V，A）），称为覆盖不等式，对STAB（Gn）是无效的.通过观察到它们提供了Mn-p（$\vec{K}$n（V，A））（p=n-2）的完整描述，证明了它们的重要性和作用.引入了一类新的不等式，称为I*-Cover不等式，该不等式具有非标准性质：对Mn-p（$\vec{K}$n（V，A））不成立，但不截断最优解.
Abstract.The p-Median problem defined on a complete directed graph with n nodes ($\vec{K}$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($\vec{K}$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($\vec{K}$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($\vec{K}$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 $\vec{K}$n(V,A).We also define a very basic class of facet-defining inequalities of Mn-p($\vec{K}$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($\vec{K}$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($\vec{K}$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.