Background

The definition of the Travelling Salesman Problem (TSP) is quite straightforward:

Given a set of n stations and distances c_ab.
For each disjoint pair a,b of stations find a roundtrip of minimal total length visiting each station exactly once.
In the symmetric TSP is c_ab = c_ba, in the asymmetric case c_ab may be different from c_ba

The MERLIN method presented here applies Linear Programming to solve the asymmetric TSP. Solving TSP with linear optimization is not a new idea. In fact, amazing solutions of particular problems with thousands of cities have been produced by using LP.  Nevertheless, these solutions haven't been general applicable but have been specifically adapted to the particular problem.

So, due to the NP-completeness of the TSP each general applicable algorithm known so far requires an exponential number of computational steps.

May be this has been changed now:
MERLIN requires O(n⁵) variables and O(n⁴) constraints for its linear formulation of the TSP. This is obviously a polynomial-bounded number and LP itself is known to be polynomial.

So, may be the question

P=NP

is settled?

I hope you will find everything you need on this page to form your own opinion and would be glad to receive your feedback (be it positive or negative).

Joachim Mertz
tsp@merlins-world.de




back