The dragon war

摘要

This article presents an approach to solve the travelling salesman problem using linear optimisation with a suitable set of constraints. Such approaches are well known as Cutting Plane methods but previously applied algorithms still suffer from the NP-completeness of the problem causing an exponential number of computational steps in the worst case. The method presented in this paper both tolerates non-integer results for a dedicated class of solutions (symmetric solutions) and avoids other ones (asymmetric solutions). It is thus able to deal with the inherent complexity of the travelling salesman problem.Therefore the overall complexity of the optimisation algorithm remains polynomial in the worst case.