25
$\begingroup$

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).

$\endgroup$
10
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ These comments perfectly make sense. However, many new papers were published on polynomial-size formulations of TSP since 1991. The early ones (Gavish and Graves, MTZ, Wong, Claus - all before 1990) have either a big practical value (MTZ, Desrochers and Laporte, Gavish and Graves) or a big theoretical value (Wong, Claus: multi-commodity flow is equivalent to DFJ). So the motivation of many newer papers since 1995 or so is still not very clear to me, but many works mention that generating DFJ cuts is less convenient if TSP is only a subproblem. $\endgroup$ – Omicron_Persei_11 Aug 8 at 18:16
  • $\begingroup$ As both the MTZ inequalities and the DFJ cuts serve as subtour-elimination constraints, I doubt that the (improved) MTZ inequalities have a large enough effect on the LP-relaxation to really speed up the solution process if DFJ cuts are generated on the fly anyway. - I think what was meant is the possibility to strengthen MTZ and get a better initial LP bound (possibly also variables bounds etc.), which in turn would result in better branching, while the initial LP bound for DFJ is the same as of assignment problem. $\endgroup$ – Omicron_Persei_11 Aug 8 at 18:32
  • 2
    $\begingroup$ This is certainly true. However, there is also a cost involved in finding this better bound, namely adding more variables and constraints, which could make it harder to solve each node. I edited my answer to explain this more clearly. $\endgroup$ – Rolf van Lieshout Aug 9 at 8:04

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.