2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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?) $\endgroup$ – D.W. May 30 '14 at 17:11
  • $\begingroup$ I tried to clarify the question. Let me know if it needs further improvements. $\endgroup$ – Seanny123 May 30 '14 at 18:02
  • $\begingroup$ 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? $\endgroup$ – D.W. May 30 '14 at 20:23
  • $\begingroup$ 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? $\endgroup$ – Seanny123 May 31 '14 at 15:08
  • $\begingroup$ 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. $\endgroup$ – D.W. Jun 2 '14 at 5:12
3
$\begingroup$

The MTZ is not an algorithm. Miller-Tucker-Zemlin formulation is a method of formulating the Travelling Salesman Problem as an instance of integer linear programming. This lets you feed the resulting integer linear programming instance into an off-the-shelf solver for integer linear programming, and let the solver solve it for you.

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.

Alternatively, you could skip using an integer linear programming solver at all, and try to solve the Travelling Salesman Problem from scratch. But good luck with that. It's an NP-complete problem, so it is unlikely you'll be able to find an efficient algorithm to solve the problem. (And just saying "use lookup tables" is not an algorithm.)

Bottom line: I think you have a confusion about how integer linear programming works, and what MTZ is. MTZ is not an algorithm for the TSP. Rather, MTZ is a way of describing the TSP in a format that you can give to an integer linear programming solver. Lookup tables aren't an option, if you're using an integer linear programming solver.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.