Representing Travelling Salesman as Linear Expression

Question

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:

Would this yield the following matrix for 5 towns?

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 !

Answer 1

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.

Answer 2

The TSP problem is a rather complex integer programming problem due to its combinatorial nature. There are several (exact and approximated) techniques to solve it. The model in Wikipedia is just one of them: it has constraints to ensure there is only one incoming and outgoing arc in each node and the constraints with u variables are for preventing sub-cycles in the solution. There is also several ways to write this sub-cycle preventing constraints, some of them can be found on section 4.1 of this article. The section presents some models for the TSP problem (all of them can be solved using CPLEX, Gurobi, MATLAB or other Integer/Linear Programming Software.

Hope I could be of any help. (=