Optimal Toll Design: A Lower Bound Framework for the Traveling Salesman Problem

Start: 03/10/2011 - 4:15pm
End  : 03/10/2011 - 4:15pm

Statistics/OR/Math Finance Seminar

Alejandro Toriello, USC


We propose a framework of lower bounds for the asymmetric traveling salesman problem (TSP) with unrestricted costs 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 present preliminary computational results and, time permitting, discuss future extensions. The talk will be mostly self-contained, assuming only knowledge of linear programming duality.

Harvey Mudd College 3rd floor Sprague. Refreshments at 4pm.