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 等数据库收录! |
|