blackpenredpen

math for fun 

  1. Discussions
  2. Math Problems
  3. Travelling Salesperson problem(TSP)
Search
Βασίλης Κέκεσης
Dec 20, 2020

Travelling Salesperson problem(TSP)

Hello, some of you might have heard of this problem before. A salesman is at the starting point of N cities

and wants to visit the remaining (N-1) cities of a network and return to the starting point by travelling the minimum distance. Each city is visited only once. Usually a table with the distance between the cities is given.

For example, for N = 7 the following table is given:






Basically, this is a linear programming problem that can be solved with the Miller ,Tucker and Zemmlin formulation, which is the following:













I understand that the 1nd constraint is to require that each city is arrived at from exactly one city and the 2nd is to require that from each city there is a departure to exactly one other city. However, I don't understand what the 3rd constraint wants to show. I would appreciate if anyone could explain and write down how this constraint is applied to the problem above.

0