A Polyhedral Approach to the Asymmetric Traveling Salesman Problem
提出分支切割算法，利用非对称旅行商问题特有的面定义割，配合新分离算法和变量定价技术，在难解实例上显著优于现有基于指派问题的算法。
Several branch-and-bound algorithms for the exact solution of the asymmetric traveling salesman problem (ATSP), based on the assignment problem (AP) relaxation, have been proposed in the literature. These algorithms perform very well for some instances (e.g., those with uniformly random integer costs), but very poorly for others. The aim of this paper is to evaluate the effectiveness of a branch-and-cut algorithm exploiting ATSP-specific facet-defining cuts, to be used to attack hard instances that cannot be solved by the AP-based procedures from the literature. We present new separation algorithms for some classes of facet-defining cuts, and a new variable-pricing technique for dealing with highly degenerate primal LP problems. A branch-and-cut algorithm based on these new results is designed and evaluated through computational analysis on several classes of both random and real-world instances. The outcome of the research is that, on hard instances, the branch-and-cut algorithm clearly outperforms the best AP-based algorithms from the literature.