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

DOI10.1007/s10107-013-0631-6zbMath1327.90121MaRDI 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 problem; integer program; dynamic program; lower bound technique; approximate linear program

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C10: Integer programming

90C27: Combinatorial optimization

90C39: Dynamic programming

Related Items

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, 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