New tighter polynomial length formulations for the asymmetric traveling salesman problem with and without precedence constraints

DOI10.1016/j.orl.2004.03.007zbMath1076.90062OpenAlexW2004882088MaRDI QIDQ1886799

Hanif D. Sherali, Ajay Bhootra, Sarin, Subhash C.

Publication date: 19 November 2004

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2004.03.007

zbMATH Keywords

Precedence constraintsAsymmetric traveling salesman problemSubtourelimination constraints

Mathematics Subject Classification ID

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

Related Items (22)

Models for a Steiner multi-ring network design problem with revenues ⋮ Enhanced compact models for the connected subgraph problem and for the shortest path problem in digraphs with negative cycles ⋮ Multiple asymmetric traveling salesmen problem with and without precedence constraints: performance comparison of alternative formulations ⋮ Minimizing conditional-value-at-risk for stochastic scheduling problems ⋮ Formulations for the clustered traveling salesman problem with \(d\)-relaxed priority rule ⋮ Formulations and a Lagrangian relaxation approach for the prize collecting traveling salesman problem ⋮ A data-guided lexisearch algorithm for the asymmetric traveling salesman 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 ⋮ Optimization of logistics services in hospitals ⋮ Natural and extended formulations for the time-dependent traveling salesman problem ⋮ 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 ⋮ Hybrid optimization methods for time-dependent sequencing problems ⋮ Selective and periodic inventory routing problem for waste vegetable oil collection ⋮ New formulation for the high multiplicity asymmetric traveling salesman problem with application to the Chesapeake problem ⋮ A class of lifted path and flow-based formulations for the asymmetric traveling salesman problem with and without precedence constraints ⋮ Strong multi-commodity flow formulations for the asymmetric traveling salesman problem ⋮ Requiem for the Miller-Tucker-Zemlin subtour elimination constraints? ⋮ A Set Covering Approach for the Double Traveling Salesman Problem with Multiple Stacks ⋮ Pickup and delivery problem with incompatibility constraints

Cites Work

• Unnamed Item
• An analytical comparison of different formulations of the travelling salesman problem
• A Lagrangian relax-and-cut approach for the sequential ordering problem with precedence relationships
• A branch \& cut algorithm for the asymmetric traveling salesman problem with precedence constraints
• Compact vs. exponential-size LP relaxations
• The asymmetric travelling salesman problem and a reformulation of the Miller-Tucker-Zemlin constraints
• The precedence-constrained asymmetric traveling salesman polytope
• Improvements and extensions to Miller-Tucker-Zemlin subtour elimination constraints
• Integer Programming Formulation of Traveling Salesman Problems
• On Tightening the Relaxations of Miller-Tucker-Zemlin Formulations for Asymmetric Traveling Salesman Problems
• Solution of a Large-Scale Traveling-Salesman Problem
• The asymmetric travelling salesman problem: on generalizations of disaggregated Miller-Tucker-Zemlin constraints

This page was built for publication: New tighter polynomial length formulations for the asymmetric traveling salesman problem with and without precedence constraints