Computational experiments for mixed-integer programming

• Grant number: 14/02206-8
• Support Opportunities: Scholarships abroad - Research Internship - Scientific Initiation
• Start date: May 15, 2014
• End date: August 14, 2014
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Orlando Lee
• Grantee: Allan Sapucaia Barboza
• Supervisor: Ricardo Fukasawa
• Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil
• Institution abroad: University of Waterloo, Canada
• Associated to the scholarship: 13/12551-1 - Study and comparison of algorithms for network flows problems, BP.IC

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)