Strong multi-commodity flow formulations for the asymmetric traveling salesman problem

DOI10.1016/j.ejor.2018.05.021zbMath1403.90558OpenAlexW2803820630WikidataQ129814484 ScholiaQ129814484MaRDI QIDQ724060

Safa Ben Salem, Ali Balma, Mehdi Mrad, Talel Ladhari

Publication date: 25 July 2018

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2018.05.021

zbMATH Keywords

traveling salesmanreformulation-linearization techniquesequential ordering problemcompact formulations

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Transportation, logistics and supply chain management (90B06) Combinatorial optimization (90C27)

Related Items (3)

Formulations for the clustered traveling salesman problem with \(d\)-relaxed priority rule ⋮ Tight lower bounds for the traveling salesman problem with draft limits ⋮ An asymmetric traveling salesman problem based matheuristic algorithm for flowshop group scheduling problem

Uses Software

• TSPLIB
• CPLEX

Cites Work

• Unnamed Item
• A comparative analysis of several asymmetric traveling salesman problem formulations
• A hierarchy of relaxations and convex hull characterizations for mixed- integer zero-one programming problems
• A node current-based 2-index formulation for the fixed-destination multi-depot travelling salesman problem
• The asymmetric travelling salesman problem and a reformulation of the Miller-Tucker-Zemlin constraints
• New tighter polynomial length formulations for the asymmetric traveling salesman problem with and without precedence constraints
• Improvements and extensions to Miller-Tucker-Zemlin subtour elimination constraints
• 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?
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Integer Programming Formulation of Traveling Salesman Problems
• A New Formulation for the Travelling Salesman Problem
• On Tightening the Relaxations of Miller-Tucker-Zemlin Formulations for Asymmetric Traveling Salesman Problems
• TSPLIB—A Traveling Salesman Problem Library
• A Survey of Different Integer Programming Formulations of the Travelling Salesman Problem
• Solution of a Large-Scale Traveling-Salesman Problem

This page was built for publication: Strong multi-commodity flow formulations for the asymmetric traveling salesman problem