[Solved]: Advantage of MTZ problem formulation of TSP

Problem Detail: 

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?

Asked By : Seanny123

Answered By : D.W.

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/26216