×

zbMATH — the first resource for mathematics

Requiem for the Miller-Tucker-Zemlin subtour elimination constraints? (English) Zbl 1304.90168
Summary: The Miller-Tucker-Zemlin (MTZ) Subtour Elimination Constraints (SECs) and the improved version by Desrochers and Laporte (DL) have been and are still in regular use to model a variety of routing problems. This paper presents a systematic way of deriving inequalities that are more complicated than the MTZ and DL inequalities and that, in a certain way, “generalize” the underlying idea of the original inequalities. We present a polyhedral approach that studies and analyses the convex hull of feasible sets for small dimensions. This approach allows us to generate generalizations of the MTZ and DL inequalities, which are “good” in the sense that they define facets of these small polyhedra. It is well known that DL inequalities imply a subset of Dantzig-Fulkerson-Johnson (DFJ) SECs for two-node subsets. Through the approach presented, we describe a generalization of these inequalities which imply DFJ SECs for three-node subsets and show that generalizations for larger subsets are unlikely to exist. Our study presents a similar analysis with generalizations of MTZ inequalities and their relation with the lifted circuit inequalities for three node subsets.

MSC:
90C27 Combinatorial optimization
90C35 Programming involving graphs or networks
Software:
PORTA; TSPLIB
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Christof, T., & Löbel, A. (2004). PORTA: POlyhedron Representation Transformation Algorithm. <http://www.zib.de/Optimization/Software/Porta/>.
[2] Dantzig, G. B.; Fulkerson, D. R.; Johnson, S. M., Solution of a large-scale traveling salesman problem, Operations Research, 2, 393-410, (1954) · Zbl 1414.90372
[3] Desrochers, M.; Laporte, G., Improvements and extensions to the Miller-Tucker-zemlin subtour elimination constraints, Operations Research Letters, 10, 27-36, (1991) · Zbl 0723.90081
[4] Fischetti, M., Facets of the asymmetric traveling salesman problem, Mathematics of Operations Research, 16, 42-56, (1991) · Zbl 0742.90079
[5] Gavish, B., & Graves, S. C. (1978). The traveling salesman problem and related problems. Working Paper GR-078-78, Operations Research Center, Massachusetts Institute of Technology.
[6] Godinho, M. T.; Gouveia, L.; Pesneau, P., On a time-dependent formulation and an updated classification of atsp formulations, (Mahjoub, A. R., Progress in combinatorial optimization, (2011), Wiley), 223-254 · Zbl 1263.90074
[7] Gouveia, L., Using the Miller-Tucker-zemlin constraints to formulate a minimal spanning tree problem with hop constraints, Computers and Operations Research, 2, 959-970, (1996) · Zbl 0854.90139
[8] Gouveia, L.; Pesneau, P., On extended formulations for the precedence constrained asymmetric traveling salesman problem, Networks, 48, 77-89, (2006) · Zbl 1103.90084
[9] Gouveia, L.; Pires, J. M., The asymmetric travelling salesman problem and a reformulation of the Miller-Tucker-zemlin constraints, European Journal of Operational Research, 112, 134-146, (1999) · Zbl 0971.90099
[10] Gouveia, L.; Pires, J. M., The asymmetric travelling salesman problem: on generalizations of disaggregated Miller-Tucker-zemlin constraints, Discrete Applied Mathematics, 112, 129-145, (2001) · Zbl 1054.90059
[11] Grötschel, M.; Padberg, M., Polyhedral theory, (Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A.; Shmoys, D. B., The traveling salesman problem: A guided tour of combinatorial optimization, (1985), Wiley New York) · Zbl 0587.90073
[12] Langevin, A.; Soumis, F.; Desrosiers, J., Classification of traveling salesman problem formulations, Operations Research Letters, 9, 127-132, (1990) · Zbl 0697.90057
[13] Lawler, E. L.; Lenstra, J. K.; Rinnooy Kann, A. H.G.; Shmoys, D. B., The travelling salesman problem, (1985), Wiley Chichester · Zbl 0563.90075
[14] Marcotte, P.; Savard, G.; Semet, F., A bilevel programming approach to the travelling salesman problem, Operations Research Letters, 32, 240-248, (2004) · Zbl 1045.90052
[15] Miller, C. E.; Tucker, A. W.; Zemlin, R. A., Integer programming formulations and traveling salesman problems, Journal of Association for Computing Machinery, 7, 326-329, (1960) · Zbl 0100.15101
[16] Öncan, T.; Altinel, I. K.; Laporte, G., A comparative analysis of several asymmetric traveling salesman problem formulations, Computers & Operations Research, 36, 637-654, (2009) · Zbl 1179.90321
[17] Padberg, M.; Sung, T., An analytical comparison of different formulations of the travelling salesman problem, Mathematical Programming, 52, 315-357, (1991) · Zbl 0770.90075
[18] Roberti, R.; Toth, P., Models and algorithms for the asymmetric traveling salesman problem: an experimental comparison, EURO Journal on Transportation and Logistics, 1, 113-133, (2012)
[19] Sarin, S. C.; Sherali, H. D.; Bhootra, A., New tighter polynomial length formulations for the asymmetric traveling salesman problem with and without precedence constraints, Operations Research Letters, 33, 62-70, (2005) · Zbl 1076.90062
[20] Sherali, H. D.; Driscoll, P. J., On tightening the relaxations of Miller-Tucker-zemlin formulations for asymmetric travelling salesman problems, Operations Research, 50, 4, 656-669, (2002) · Zbl 1163.90776
[21] Sherali, H. D.; Sarin, S. C.; Tsai, P. F., A class of lifted path and flow-based formulations for the asymmetric traveling salesman problem with and without precedence constraints, Discrete Optimization, 3, 20-32, (2006) · Zbl 1109.90075
[22] TSPLIB (1997). A library of travelling salesman and related problem instances. <http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsplib.html> Accessed 17.07.12.
[23] Wong, R. 1980. Integer programming formulations of the travelling salesman problem. In Proceedings of the IEEE international conference of circuits and computers (pp. 149-152).
[24] Yaman, H., Formulations and valid inequalities for the heterogeneous vehicle routing problem, Mathematical Programming, 106, 365-390, (2006) · Zbl 1134.90527
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.