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.