The rationale to improve MTZ?

Question

Currently I need to solve a quite specific problem involving symmetric TSP as a sub-problem (i.e., a Hamiltonian cycle is a necessary condition for optimizing some problem-specific variables that should make use of that cycle).

From the literature review, the Dantzig-Fulkerson-Johnson (DFJ) formulation seems to be the tightest and most practical TSP formulation. However, I have also encountered a large number of papers trying to improve the Miller-Tucker-Zemlin (MTZ) formulation that is more convenient than DFJ but very loose (e.g., papers by Desrochers-Laporte, H. Sherali etc.). Why would people spend time improving MTZ, if DFJ is much tighter and all compact MTZ improvements never come close to DFJ?

In the paper by H. Sherali and P. Driscoll (2002), the authors mention that generating DFJ constraints via branch-and-cut may be "inconvenient" if TSP is only a substructure within the model (precisely my situation). However, I don't understand why would it be inconvenient? Some other authors mention that it is important to tighten the polyhedral representation of the initial TSP formulation to use the best bounds produced by the linear programming relaxation of the initial formulation that guides branching decisions, regardless of the run-time actions taken by the MIP optimizers. Can it really be so that a good initial formulation may outweigh the benefits of strong DFJ cuts generated during the run-time?

Finally, if there is indeed any merit in improved MTZ-like TSP formulations (e.g., Desrochers and Laporte (1991)), would it make sense to use such improved MTZ formulations to support the TSP subproblem, while still generating valid DFJ cuts in the run-time?

P.S.: Some MTZ-papers are as new as 2018, so I am wondering if such new formulations can outperform DFJ on problems which only include TSP as a sub-problem (otherwise why so many papers; for pure TSP DFJ should be much better, this is clear).

Answer 1

Why would people spend time improving MTZ, if DFJ is much tighter and all compact MTZ improvements never come close to DFJ?

Although this might not be used in TSP solvers, it could still be interesting to research finding tight compact formulations for the TSP from a theoretical perspective.

In the paper by H. Sherali and P. Driscoll, the authors mention that generating DFJ constraints via branch-and-cut may be "inconvenient" if TSP is only a substructure within the model (precisely my situation). However, I don't understand why would it be inconvenient?

I suppose that implementing branch-and-cut is more time-consuming than simply implementing the MTZ formulation. If the TSP substructure contains a small number of nodes, the MTZ formulation might work fine and the benefits of the tighter DFJ formulation are not worth the effort.

Can it really be so that a good initial formulation may outweigh the benefits of strong DFJ cuts generated during the run-time?

Did the authors you mentioned perform any experiments to back up this claim? If not, you might want to take this with a grain of salt. A good initial formulation may indeed lead to better bounds and therefore a smaller branch-and-bound tree. On the other hand, strengthening MTZ requires introducing more variables and constraints. For example, the improved MTZ-formulation by Sherali and Driscoll (2002) contains $2n^2$ variables and $2n^2+3n$ constraints. As a result, solving each node in the tree might be more time-consuming. Only experiments can show which of these forces is stronger. However, a significant speed-up would be required for such an approach to become competitive with a branch-and-cut algorithm for the DFJ formulation.

Finally, if there is indeed any merit in improved MTZ-like TSP formulations (e.g., Desrochers-Laporte 1991), would it make sense to use such improved MTZ formulations to support the TSP subproblem, while still generating valid DFJ cuts in the run-time?

This strongly relates to your third question. My suggestion would be to at least not try this as your first approach. Rather, start with either the MTZ formulation or a branch-and-cut algorithm to solve the DFJ formulation. If this does not lead to satisfactory results, you could try some more exotic approaches.