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

DOI10.1002/NET.21765MaRDI QIDQ4584873zbMATH OpenOpenAlexWikidataFDO

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

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)

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

Cited in

(8)

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

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)