**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

In the symmetric TSP is

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^{5}) variables and O(n^{4})
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