Advanced search
Start date

Computational experiments for mixed-integer programming

Grant number: 14/02206-8
Support Opportunities:Scholarships abroad - Research Internship - Scientific Initiation
Effective date (Start): May 15, 2014
Effective date (End): 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
Research place: University of Waterloo, Canada  
Associated to the scholarship:13/12551-1 - Study and comparison of algorithms for network flows problems, BP.IC


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)

News published in Agência FAPESP Newsletter about the scholarship:
Articles published in other media outlets (0 total):
More itemsLess items

Please report errors in scientific publications list by writing to: