The asymmetric travelling salesman problem: on generalizations of disaggregated Miller-Tucker-Zemlin constraints

DOI10.1016/S0166-218X(00)00313-9zbMath1054.90059OpenAlexW2084839533WikidataQ127647437 ScholiaQ127647437MaRDI QIDQ5946820

Jose Manuel Pires, Luís Gouveia

Publication date: 30 July 2002

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(00)00313-9

zbMATH Keywords

Multicommodity flowsAggregationAsymmetric travelling salesman problemGeneralized Miller-Tucker-Zemlin constraintsLifted circuit inequalitiesSimple FD inequalities

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Related Items (17)

New tighter polynomial length formulations for the asymmetric traveling salesman problem with and without precedence constraints ⋮ Models for a Steiner multi-ring network design problem with revenues ⋮ A new mathematical programming formulation for the single-picker routing problem ⋮ Tight lower bounds for the traveling salesman problem with draft limits ⋮ Precedence constrained generalized traveling salesman problem: polyhedral study, formulations, and branch-and-cut algorithm ⋮ Lifted polynomial size formulations for the homogeneous and heterogeneous vehicle routing problems ⋮ A conditional-logic interpretation for Miller-Tucker-Zemlin inequalities and extensions ⋮ The delivery man problem with time windows ⋮ Natural and extended formulations for the time-dependent traveling salesman problem ⋮ Combined route capacity and route length models for unit demand vehicle routing problems ⋮ Polyhedral results and a branch-and-cut algorithm for the double traveling salesman problem with multiple stacks ⋮ A comparative analysis of several asymmetric traveling salesman problem formulations ⋮ Selective and periodic inventory routing problem for waste vegetable oil collection ⋮ Models for a Steiner ring network design problem with revenues ⋮ A class of lifted path and flow-based formulations for the asymmetric traveling salesman problem with and without precedence constraints ⋮ Requiem for the Miller-Tucker-Zemlin subtour elimination constraints? ⋮ Equivalent cyclic polygon of a euclidean travelling salesman problem tour and modified formulation

Cites Work

• Unnamed Item
• Unnamed Item
• Classification of travelling salesman problem formulations
• The asymmetric travelling salesman problem and a reformulation of the Miller-Tucker-Zemlin constraints
• Using the Miller-Tucker-Zemlin constraints to formulate a minimal spanning tree problem with Hop constraints
• Improvements and extensions to Miller-Tucker-Zemlin subtour elimination constraints
• Lifted Cycle Inequalities for the Asymmetric Traveling Salesman Problem
• Integer Programming Formulation of Traveling Salesman Problems
• A New Formulation for the Travelling Salesman Problem
• Facets of the Asymmetric Traveling Salesman Polytope
• The Fixed-Outdegree 1-Arborescence Polytope
• A Polyhedral Approach to the Asymmetric Traveling Salesman Problem
• Models for a Steiner ring network design problem with revenues

This page was built for publication: The asymmetric travelling salesman problem: on generalizations of disaggregated Miller-Tucker-Zemlin constraints