...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Mathematical Programming >On the graphical relaxation of the symmetric traveling salesman polytope
【24h】

On the graphical relaxation of the symmetric traveling salesman polytope

机译：关于对称旅行推销员多面体的图形松弛

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

摘要

The Graphical Traveling Salesman Polyhedron (GTSP) has been proposed by Naddef and Rinaldi to be viewed as a relaxation of the Symmetric Traveling Salesman Polytope (STSP). It has also been employed by Applegate, Bixby, Chvatal, and Cook for solving the latter to optimality by the branch-and-cut method. There is a close natural connection between the two polyhedra. Until now, it was not known whether there are facets in TT-form of the GTSP polyhedron which are not facets of the STSP polytope as well. In this paper we give an affirmative answer to this question for n >= 9. We provide a general method for proving the existence of such facets, at the core of which lies the construction of a continuous curve on a polyhedron. This curve starts in a vertex, walks along edges, and ends in a vertex not adjacent to the starting vertex. Thus there must have been a third vertex on the way.
机译：图形旅行推销员多面体（GTSP）由Naddef和Rinaldi提出，被视为对对称旅行推销员多面体（STSP）的放松。它也被Applegate，Bixby，Chvatal和Cook所采用，用于通过分支剪切法将后者求解到最优。两个多面体之间有着紧密的自然联系。到现在为止，还不知道是否存在TTSP形式的GTSP多面体的小平面，这些小平面也不是STSP多面体的小平面。在本文中，对于n> = 9，我们对这个问题给出肯定的答案。我们提供了证明这种刻面存在的通用方法，其核心在于在多面体上构造连续曲线。该曲线在一个顶点处开始，沿着边缘移动，并在一个不与起始顶点相邻的顶点处结束。因此，必定会有第三个顶点。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号