A POLYHEDRAL APPROACH TO THE ASYMMETRIC TRAVELING SALESMAN PROBLEM

Several branch-and-bound algorithms for the exact solution of the asym metric traveling salesman problem (ATSP), based on the assignment prob lem (AP) relaxation, have been proposed in the literature. These algor ithms perform very well for some instances (e.g., those with uniformly random integer costs), but very poorly for others. The aim of this pa per is to evaluate the effectiveness of a branch-and-cut algorithm exp loiting ATSP-specific facet-defining cuts, to be used to attack hard i nstances that cannot be solved by the AP-based procedures from the lit erature. We present new separation algorithms for some classes of face t-defining cuts, and a new variable-pricing technique for dealing with highly degenerate primal LP problems. A branch-and-cut algorithm base d 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 t he literature.