A Branch-and-Cut Approach to a Traveling Salesman Problem with Side Constraints
将1987年AIAA设计挑战问题建模为零一线性规划，证明在忽略或线性化非线性约束时松弛问题可多项式求解，并开发了AIAA/SOLVER软件用分支切割法在弱随机成本假设下求最优解。
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.