This model deals with the well-known Traveling Salesman Problem (TSP). It is the first of a series that show different MIP formulations to solve the problem.

The data for the models comes from TSPLIB.The problem br17 we used is a small asymmetric TSP. The models are solely for illustration: large scale TSP's are not solved this way.

In this first model we first solve a relaxation of the problem by ignoring the subtour elimination restrictions. The resulting problem is called the assignment problem:

min c'x
s.t.  1'x = 1'
x'1 = 1
x binary

The optimal solution of this problem will likely contain subtours. Some GAMS code is written to detect and show these subtours.

Subsequently we introduce cuts that exclude the current solution, and resolve. We repeat this until a solution without subtours is found. In general these cuts are of the form:

sum(P(i,j),x(P)) - sum(Q(i,j),x(Q)) <= |P|-1

where P is the set of variables that have assumed the value 1 in the current solution and Q is the set of variables that are zero in the current solution. |P| is the number of elements in the set P. To see that this works consider the solution x=(1, 0, 1). The constraint: x1-x2+x3=L=1 will prohibit this solution, while allowing all other possible solutions.

For the special case of this model, we can use the cuts:

sum(P(i,j),x(P)) <= |P|-1

as they do not exclude any feasible solutions.

As we just eliminate one solution after another the number of cycles we have to do is very large. Therefore we show this formulation only for a small subset of the original problem: only the first six cities out of 17 are considered.

For general integer cuts (these are more difficult) see the library model icut.