A Branch-and-Cut Approach to a Traveling Salesman Problem with Side Constraints

M. Padberg and G. Rinaldi
Additional contact information
M. Padberg: School of Business, New York University, New York, New York 10003
G. Rinaldi: Istituto di Analisi dei Sistemi ed Informatica del CNR, Viale Manzoni 30, 00185 Roma, Italy

Management Science, 1989, vol. 35, issue 11, 1393-1412

Abstract: A problem posed by O. L. Deutsch (Deutsch, O. L. 1988. Artificial intelligence design challenge---Background, analysis, and relative performance of algorithms. J. Guidance, Control, and Dynamics 11 386--393.) as the Artificial Intelligence Design Challenge for the 1987 American Institute of Aeronautics and Astronautics (AIAA) Conference on Guidance, Navigation & Control (Monterey, CA, August 17--19, 1987) is formulated as a zero-one linear program. We show that the associated (relaxed) linear programming problem can be solved in polynomial time despite an exponential size of the proposed constraint system in terms of the underlying parameter n of the number of cities considered, when a nonlinear constraint of the problem is either ignored or approximated by linearization. We describe a software system AIAA/SOLVER that we have implemented to solve the problem to optimality under an apparently weak assumption about its stochastic cost structure using branch-and-cut.

Keywords: cutting planes; traveling salesman problem; branch and cut; numerical computation; polyhedral theory; heuristics (search for similar items in EconPapers)
Date: 1989
References: Add references at CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.35.11.1393 (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:35:y:1989:i:11:p:1393-1412

Access Statistics for this article

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