Optimal toll design: a lower bound framework for the asymmetric traveling salesman problem

DOI10.1007/s10107-013-0631-6zbMath1327.90121OpenAlexW2129480990MaRDI QIDQ2452379

Alejandro Toriello

Publication date: 2 June 2014

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-013-0631-6

zbMATH Keywords

traveling salesman probleminteger programdynamic programlower bound techniqueapproximate linear program

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Combinatorial optimization (90C27) Dynamic programming (90C39)

Related Items

A Polyhedral Approach to Online Bipartite Matching ⋮ Network-Based Approximate Linear Programming for Discrete Optimization ⋮ Probabilistic prediction of the complexity of traveling salesman problems based on approximating the complexity distribution from experimental data ⋮ A polyhedral approach to online bipartite matching

Uses Software

• Concorde

Cites Work

• Unnamed Item
• Analyzing the Held-Karp TSP bound: A monotonicity property with application
• Generalized polynomial approximations in Markovian decision processes
• The travelling salesman problem as a constrained shortest path problem: Theory and computational experience
• A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem
• Maximizing a submodular function by integer programming: Polyhedral results for the quadratic case
• The traveling salesman problem and its variations
• Worst-case comparison of valid inequalities for the TSP
• Approximate extended formulations
• A Dynamic Programming Approach to Sequencing Problems
• Heuristic analysis, linear programming and branch and bound
• On the worst-case performance of some algorithms for the asymmetric traveling salesman problem
• SPLINE APPROXIMATIONS TO VALUE FUNCTIONS
• Dynamic Programming Strategies for the Traveling Salesman Problem with Time Window and Precedence Constraints
• The Traveling-Salesman Problem and Minimum Spanning Trees
• The traveling-salesman problem and minimum spanning trees: Part II
• Duality and Existence of Optimal Policies in Generalized Joint Replenishment