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 !

Wisp

The more I go on, the more I realise this may be more mathematical and maybe should be moved to math.stackexchange? – Wisp

It would not "yield that matrix", because you don't choose values for the x_{ij} variables -- the ILP solver does. You give it a bunch of variables, as well as some constraints on those variables, and an objective function of the variables, and it (somewhat magically) finds values for each of them that (a) satisfy all the constraints and (b) achieves the minimum (or maximum) value of the objective function. – Mcdaniels

I may be asking for a lot here, but have you any idea how to write these constraints as a linear expression so the ILP solver can in fact solve the TSP. Even a link or a hint would be great, or even a confirmation that this is even possible? – Wisp

It is written on the Wikipedia page, though admittedly in a very compact way. Suppose there are just 4 vertices in your graph, 1, 2, 3 and 4. Then there are 4*3 = 12 possible directed edges (two between each vertex pair -- one in each direction), so we need 12 variables that can be either 0 or 1. Let's call the variable that will record whether the edge between from vertex 1 to vertex 2 is in the optimal solution or not x_12, etc. Then, e.g., the constraint that exactly 1 edge leaves vertex 1 would be written "x_12 + x_13 + x_14 = 1". – Mcdaniels

And the constraint that exactly 1 edge enters vertex 1 would be written "x_21 + x_31 + x_41 = 1". I don't understand the bottommost constraint on the Wikipedia page, but I do understand why just giving all possible edge-leaving and edge-entering constraints (like the 2 I just described) isn't sufficient to find a tour: it's because these constraints do nothing to prevent multiple totally separate tours from being generated. – Mcdaniels

Hmm... I think it's beginning to click, I'm still unsure of the artificial variable u and its significance – Wisp

I can't spare the time to help you there I'm afraid. What you can do though, is to solve the problem with ILP using just the edge-leaving and edge-entering constraints, and check the answer: if it contains just a single cycle then you have the optimal solution, otherwise add in some more constraints to forbid the particular invalid solution you just got, and re-solve. This is a standard ILP approach called "cutting planes" -- googling "subtour elimination constraints" should help. – Mcdaniels

If you just want to solve some TSP instances, there's an app for that. – Leporine

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.

Fayfayal

As you can see above, I've been trying to understand that article with confusion. I can understand the constraints but have difficulty writing them as a linear expression. Are you implying that software such as CPLEX cannot solve such a system of equations? Or must we specify it as an integer linear program. I'm a bit confused there. Thanks for the answer. – Wisp

I don't know exactly whether or not CPLEX can solve integer linear programs, but I think so; however the point I was trying to make is that modelling as (non-integral) linear program is very likely to be impossible. – Fayfayal

Modeling it as a non-integer linear problem doesn't directly give the solution (usually), but it is very useful as a bound in Branch and Bound, so there's that. That way you can also add more advanced cuts based on properties of a tour (comb cut, blossom cut), instead of just standard cuts that you'd get in an ILP solver. Of course that means that in total you're still solving ILP. – Gloom

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. (=

Leftwards