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

被引:0
|
作者
Alejandro Toriello
机构
[1] University of Southern California,Daniel J. Epstein Department of Industrial and Systems Engineering
来源
Mathematical Programming | 2014年 / 144卷
关键词
Traveling salesman problem; Dynamic program; Approximate linear program; Integer program; Lower bound technique; 90C10; 90C27; 90C35; 90C39;
D O I
暂无
中图分类号
学科分类号
摘要
We propose a framework of lower bounds for the asymmetric traveling salesman problem (TSP) based on approximating the dynamic programming formulation with different basis vector sets. We discuss how several well-known TSP lower bounds correspond to intuitive basis vector choices and give an economic interpretation wherein the salesman must pay tolls as he travels between cities. We then introduce an exact reformulation that generates a family of successively tighter lower bounds, all solvable in polynomial time. We show that the base member of this family yields a bound greater than or equal to the well-known Held-Karp bound, obtained by solving the linear programming relaxation of the TSP’s integer programming arc-based formulation.
引用
收藏
页码:247 / 264
页数:17
相关论文
共 50 条