# Advantage of MTZ problem formulation of TSP

In class, we saw the Miller-Tucker-Zemlin formulation of the Travelling Salesmen Problem (TSP). MTZ is a way of formulating the TSP as an integer linear programming instance.

I understand how MTZ works, but I'm confused why MTZ is considered a better algorithm for checking for sub-cycles and rejecting them as answers than just keeping a list of connected nodes.

I can imagine a look-up table of each node along with a corresponding boolean that defines whether a node is connected or not. Consequently, the running time of checking if a connection is valid would be O(1). If it isn't a run-time consideration, what is the reason that MTZ is preferred?

• The citation seems to be missing. Would you like to edit your question to give a link to a description of the MTZ formulation? Also, I'm not clear what you are thinking of as the baseline algorithm (I don't know what you mean by "keeping a list of connected nodes....look-up table..." -- can be be more specific about the alternative algorithm you are imagining?) – D.W. May 30 '14 at 17:11
• I tried to clarify the question. Let me know if it needs further improvements. – Seanny123 May 30 '14 at 18:02
• I still don't understand what your alternative algorithm is. How does keeping a list of connected nodes solve the TSP? You're going to need to spell that out more. OK, say I have a lookup table as you suggest. Now how do I use that to solve the TSP? I suspect you have some algorithm in your head, but I can't tell what that algorithm is -- and thus I can't tell whether the algorithm in your head actually works (to solve the TSP) or not. I wonder if it's possible that you have underestimated what it takes to solve the TSP. You know that it is NP-complete, right? – D.W. May 30 '14 at 20:23
• Okay, I understand where I let the confusion slip in. I assumed everyone that studied TSP also studied MTZ. This was a silly assumption. I have now tried to clarify that the MTZ is for checking for sub-cycles in a solution and rejecting them and the algorithm I propose also fits this purpose. Did I improve my question sufficiently? – Seanny123 May 31 '14 at 15:08
• I think you have a fundamental misunderstanding (lookup tables can't be used in an integer program). If the question is re-opened I'll provide a more elaborate answer. – D.W. Jun 2 '14 at 5:12

Remember that an instance of integer linear programming is a set of variables and linear inequalities. Lookup tables are not allowed; the inequalities have to be linear (e.g., $5x_1 + x_2 \le 7$, but not $T[x_1] \le 5$). Therefore, using lookup tables are simply not an option, if you want to use integer linear programming.