Combining and projecting flow models for the (precedence constrained) asymmetric traveling salesman problem

DOI10.1002/NET.21765zbMATH Open1394.90481OpenAlexW2750078990WikidataQ58169404 ScholiaQ58169404MaRDI QIDQ4584873FDOQ4584873

Authors: Luis Gouveia, Pierre Pesneau, Mario Ruthmair, Daniel Santos 

Publication date: 4 September 2018

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://hal.inria.fr/hal-01655793/file/combining-projecting-flow.pdf

Recommendations

• On extended formulations for the precedence constrained asymmetric traveling salesman problem
• New tighter polynomial length formulations for the asymmetric traveling salesman problem with and without precedence constraints
• A class of lifted path and flow-based formulations for the asymmetric traveling salesman problem with and without precedence constraints
• Multiple asymmetric traveling salesmen problem with and without precedence constraints: performance comparison of alternative formulations
• The precedence-constrained asymmetric traveling salesman polytope

zbMATH Keywords

integer linear programmingvalid inequalitiesprecedence constraintstraveling salesmanreformulationcutting plane algorithm

Mathematics Subject Classification ID

Methods of successive quadratic programming type (90C55) Linear programming (90C05) Programming involving graphs or networks (90C35) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27) Mixed integer programming (90C11)

Cited In (8)

• Precedence constrained generalized traveling salesman problem: polyhedral study, formulations, and branch-and-cut algorithm
• On extended formulations for the precedence constrained asymmetric traveling salesman problem
• Formulations for the clustered traveling salesman problem with \(d\)-relaxed priority rule
• The multiple Steiner TSP with order constraints: complexity and optimization algorithms
• Compact formulations for multi-depot routing problems: theoretical and computational comparisons
• Multiple asymmetric traveling salesmen problem with and without precedence constraints: performance comparison of alternative formulations
• Strong multi-commodity flow formulations for the asymmetric traveling salesman problem
• A class of lifted path and flow-based formulations for the asymmetric traveling salesman problem with and without precedence constraints

This page was built for publication: Combining and projecting flow models for the (precedence constrained) asymmetric traveling salesman problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4584873)