When

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

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

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

Category

Statistics/OR/Math Finance Seminar

Speaker

Alejandro Toriello, USC

Abstract

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.

Where

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