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

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 Dynamics11 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.