A Polyhedral Approach to the Asymmetric Traveling Salesman Problem

Matteo Fischetti and Paolo Toth
Additional contact information
Matteo Fischetti: DMI, University of Udine, Udine, Italy
Paolo Toth: DEIS, University of Bologna, Bologna, Italy

Management Science, 1997, vol. 43, issue 11, 1520-1536

Abstract: 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.

Keywords: traveling salesman problem; branch-and-cut algorithms; separation; computational analysis (search for similar items in EconPapers)
Date: 1997
References: Add references at CitEc
Citations: View citations in EconPapers (24)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.43.11.1520 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:43:y:1997:i:11:p:1520-1536

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().