Representation of a travel seller as a linear expression

Question

I saw online that you can write a traveling salesman problem as a linear expression and compute it using software like CPLEX for java.

I have 1000 cities and need to find a short distance. I plan to split these 1000 cities into clusters of 100 cities and run a 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 cities, and I'm sure everyone knows how TSP works.

I literally don't know how I can write linear constraints, goals, and variables that satisfy the TSP.

Can someone explain to me how this is done, or send me a link that clearly explains this, because I understand a lot and can not find anything.

EDIT:

A bit of additional information I found:

We put cities with numbers from 0 to n and define a matrix:

Will this give the following matrix for 5 cities?

Limitations:

i) Each city must come from one other city

ii) From each city, fly to the same city

iii) The route is not divided into separate islands.

Again, this makes all the sense to me, but it's still hard for me to write these constraints as a linear expression. Apparently, this is a fairly simple matrix.

Thanks for any help!

Answer 1

According to this Wikipedia article, the traveling salesman problem can be modeled as an integer linear program, which, in my opinion, is a key issue issue. The idea is to have decision variables of permissible values ​​in {0,1} that model the selected edges on the graph. Suitable constraints must ensure that the selected edges span each node, the selected edges form a collection of loops, and there is only one connected component (which together means that there is exactly one cycle containing the entire node). Please note that the article also provides a clear statement and explains the interpretation of limitations.

Since the traveling salesman problem is NP -hard, it cannot be solved by (non-integer) linear programming if P=NP .

Answer 2

The TSP problem is a rather complex integer programming task due to its combinatorial nature. To solve it, there are several (accurate and approximated) methods. The model in Wikipedia is just one of them: it has limitations to ensure that there is only one incoming and outgoing arc in each node, and restrictions with u variables are designed to prevent sub-cycles in the solution. There are also several ways to write restrictions on preventing a subcycle, some of which can be found in section 4.1 of this article . This section presents some models of the TSP problem (they can all be solved using CPLEX, Gurobi, MATLAB, or other Integer / Linear software Programming

Hope I can help. (=