Speakers - Francisco Zaragoza

Francisco Javier Zaragoza Martínez
UAM Azcapotzalco

Title: Linear programming relaxations of arc routing problems

Abstract: Routing problems are combinatorial optimization problems in which one must traverse a graph at minimum cost following certain restrictions. Perhaps the best studied vertex routing problem is the traveling salesman problem, in which one must find a minimum cost tour of a graph visiting each vertex at least once. On the other hand, it is possible that the best studied arc routing problem is the chinese postman problem, in which one must find a minimum cost tour of a graph traversing each edge at least once. It is no coincidence that both problems have been modelled using integer programming and then solved using their linear programming relaxations. In this talk we will sketch the use of this technique in order to propose good algorithms for some NP hard arc routing problems.