First of all, I need to clarify that i'm very new to this subject, hence why this question attempts to clarify a few things for me. (sorry if i'm vague in my formulation, - but i'm not a mathematics student)
I am working with a traveling salesman problem with 10 connected vertices, that I have solved in excel as an integer program.
Now I intend to check whether my feasible solution is optimal of not.
I know that I can check this by generating a heuristically feasible solution to my TSP problem. e.g. through a cheapest insertion heuristic (lets call it Zh).
And then make a relaxation of my TSP problem Pr.
if my solution is between Zh and Pr and the interval between Zh and Pr isn't too big, i can say that my solution is very close to being optimal.
Now, here is where im in doubt. My book says, that in order to make a relaxation of my problem, I will need to make it as a Miller-Tucker-Zemlin notation.
As you can see above, this is the suggestion as to how this program should be noted.
I understand whats going on in the two first constraints. - That we make separate constraints for each vertice.
However, I have no idea what we are doing below our two constraints. The book fails to clarify what respectively uj and ui represents. Let alone explain why we have to add that constraint.
If anyone could be able to elaborate on this for me in plain english, I will be very pleased. Thanks!
The MTZ constraints are designed to eliminate subtours in a solution. A subtour is basically a loop (returning to a previously visited location). If the only return you allow is to the starting point (location 1), then you have no subtours. As an example, consider a TSP with five locations. The solution 1 - 2 - 1, 3 - 4 - 5 -3 will satisfy your first two constraints but is not a valid solution. The MTZ constraints will eliminate it.
To get an intuition for the MTZ constraints, think of $u_k$ as the value of a counter that goes up by at least one each time you go to a new location. You start at location 1 with $u_1 = 1$. The MTZ constraint says that if you go directly from location $i$ to location $j$ ($x_{ij}=1$), your counter at location $j$ must be at least one higher than it was at location $i$ ($u_j \ge u_i + 1$). This prevents you from completing a loop, since returning to location $k$ from previous location $j$ would require that $u_k \ge u_j + 1 \gt u_j \ge \dots \ge u_k$, which gets you the contradiction $u_k \gt u_k$. To avoid creating a tear in the space-time continuum when you get back to location 1, the constraint is relaxed (not enforced) there.
I've glossed over why the counter goes up at least one rather than exactly one at each new stop. Basically, it's for mathematical convenience: it's easier to relax an inequality (for pairs $i, j$ that are not consecutive, i.e., $x_{ij} =0$) than it is to relax an equation.