首页 | 本学科首页   官方微博 | 高级检索  
     


Partial linear characterizations of the asymmetric travelling salesman polytope
Authors:Martin Grötschel  Manfred W. Padberg
Affiliation:1. Institut für ?konometrie und Operations Research, Universit?t Bonn, West Germany
2. Graduate School of Business Administration, New York University, New York, N.Y., USA
Abstract:We consider the linear programming formulation of the asymmetric travelling salesman problem. Several new inequalities are stated which yield a sharper characterization in terms of linear inequalities of the travelling salesman polytope, i.e., the convex hull of tours. In fact, some of the new inequalities as well as some of the well-known subtour elimination constraints are indeed facets of the travelling salesman polytope, i.e., belong to the class of inequalities that uniquely characterize the convex hull of tours to an-city problem.
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号