A branch-and-cut approach to a traveling salesman problem with side constraints

A problem posed by O.L. Deutsch 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. The authors 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. They describe a software system AIAA/SOLVER that the authors have implemented to solve the problem to optimality under an apparently weak assumption about its stochastic cost structure using branch-and-cut.