Computational experiments for mixed-integer programming

Abstract

The traveling salesman problem (TSP) can be described as: given a set of cities and travel costs between every pair of cities, a "salesman" wishes to visit every city exactly once, and then return to the starting city, in the shortest possible total cost. The goal of this project is to study and compare the strength of two hierarchies of successively tighter lower bounds for the TSP: Approximate Linear Programming and Branch-Cut-and-Bound. This can be done empirically, by means of implementing the two different families of bounds and comparing their values in real instances. This study also can be done theoretically, attempting to prove that one family of bounds will always be better than the other, or to produce counterexamples that show that such a result is not possible. (AU)