Search code examples
algorithmlinear-algebralinear-programmingcplextraveling-salesman

Representing Travelling Salesman as Linear Expression

I've seen online that one can write the travelling salesman problem as a linear expression and compute it using software such as CPLEX for java.

I have a 1000 towns and need to find a short distance. I plan on partitioning these 1000 towns into clusters of ~100 towns and performing some linear programming algorithm on these individual clusters.

The question I have is, how exactly do I represent this as a linear expression.

So I have 100 towns and I'm sure everyone's aware of how TSP works.

I literally have no clue how I can write linear constraints, objectives and variables which satisfy the TSP.

Could someone explain to me how this is done or send me a link which explains it clearly, because I've been researching a lot and can't seem to find anything.

EDIT:

A bit of extra information I found:

We label the cities with numbers 0 to n and define the matrix:

enter image description here

Would this yield the following matrix for 5 towns?

enter image description here

The constraints are:

i) Each city be arrived at from exactly one other city

ii) From each city there is a departure to exactly one other city

iii) The route isn't broken up into separate islands.

Again, this makes complete sense to me, but I'm still having trouble writing these constraints as a linear expression. Apparently it's a simple enough matrix.

Thanks for any help !

Solution

  • According to this Wikipedia article the travelling salesman problem can be modelled as an integer linear program, which I believe to be the key issue of the question. The idea is to have decision variables of permitted values in {0,1} which model selected edges in the graph. Suitable constraints must ensure that the selected edges cover every node, the selected edges form a collection of cycles and there is only one connected component (which in total means that there is exactly one cycle which contains every node). Note that the article also gives an explicit formulation and explains the interpretations of the constraints.

    As the travelling salesman problem is NP-hard, it cannot be solved via (non-integral) linear programming unless P=NP.