Requiem for the Miller–Tucker–Zemlin subtour elimination constraints?

Tolga Bektaş and Luis Gouveia

European Journal of Operational Research, 2014, vol. 236, issue 3, 820-832

Abstract: 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.

Keywords: Asymmetric traveling salesman problem; Vehicle routing; Miller–Tucker–Zemlin constraints; Projection; Subtour elimination constraints (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (14)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S037722171300619X
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:236:y:2014:i:3:p:820-832

DOI: 10.1016/j.ejor.2013.07.038

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().