• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete optimization >Study of the pedigree polytope and a sufficiency condition for nonadjacency in the tour polytope
【24h】

Study of the pedigree polytope and a sufficiency condition for nonadjacency in the tour polytope

机译：谱系多表位和游动多表位不邻接的充分条件的研究

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

The pedigree is a combinatorial object defined over the cartesian product of certain subsets of edges in a complete graph. There is a 1-1 correspondence between the pedigrees and Hamiltonian cycles (tours) in a complete graph. Linear optimization over Hamiltonian cycles, also known as the symmetric traveling salesman problem (STSP) has several 0-1 integer and mixed integer formulations. The Multistage Insertion formulation (MI-formulation) is one such 0-1 integer formulation of the STSP. Any solution to the MI-formulation is a pedigree and vice versa. However the polytope corresponding to the pedigrees has properties not shared by the STSP polytope. For instance, (i) the pedigree polytope is a combinatorial polytope, in the sense, given any two nonadjacent vertices of the polytope ~(W1,W2), we can find two other nonadjacent vertices, ~(W3,W4), such that ~(W1)+ ~(W2=~(W3)+~(W4) and (ii) testing the nonadjacency of tours is an NP-complete problem, while the corresponding problem for the pedigrees is strongly polynomial. In this paper we demonstrate how the study of the nonadjacency structure is useful in understanding that of the tour polytope. We prove that a sufficiency condition for nonadjacency in the tour polytope is nonadjacency of the corresponding pedigrees in the pedigree polytope. This proof makes explicit use of properties of both the pedigree polytope and the MI-relaxation problem.
机译：谱系是在完整图中的某些边缘子集的笛卡尔积上定义的组合对象。在完整图中，谱系和汉密尔顿周期（游程）之间存在1-1对应关系。哈密​​顿周期上的线性优化，也称为对称旅行商问题（STSP），具有几种0-1整数和混合整数公式。多级插入配方（MI配方）是STSP的此类0-1整数配方。 MI公式的任何解决方案都是谱系，反之亦然。但是，对应于谱系的多表位具有STSP多表位不共享的属性。例如，（i）家谱多面体是组合多面体，在某种意义上，给定多面体〜（W1，W2）的任意两个不相邻的顶点，我们可以找到另外两个不相邻的顶点〜（W3，W4），这样〜（W1）+〜（W2 =〜（W3）+〜（W4）和（ii）测试行程的不相邻性是一个NP完全问题，而谱系的相应问题是强多项式。如何证明不相邻结构对了解游多面体的有用性我们证明了不满足游走多面体的充分条件是谱系多面体中相应谱系的不相邻。谱系多表位和MI松弛问题。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号