Martedì 5 aprile alle 11.30 presso il Dipartimento di Ingegneria dell’Università Roma Tre, il Prof. Ulrich Pferschy terrà un seminario su:

On the Quadratic Traveling Salesman Problem

Abstract:
The well-known Traveling Salesman Problem (TSP) asks for a shortest tour through all vertices of a graph with respect to the weights of the edges. More recently, the following generalization of TSP was introduced: In the Quadratic Traveling Salesman Problem (QTSP) there is a weight associated with every three vertices traversed in succession. As a special case, we also consider the case where these weights correspond to the turning angles of the tour and speak of the angular-metric traveling salesman problem (Angle TSP).
In this talk we apply a rather basic algorithmic idea and perform the separation of the classical subtour elimination constraints on integral solutions only. Surprisingly, it turns out that this approach is faster than the standard fractional separation procedure known from the literature. We also test the combination with strengthened subtour elimination constraints for both variants, but these turn out to slow down the computation. Furthermore, we provide a new ILP linearization for the Angle TSP that needs only a linear number of additional variables while the standard linearization requires a cubic number.
We also consider the maximization version of the QTSP. For the special case of the MaxAngle TSP we can observe an interesting geometric property if the number of vertices is odd. We show that the sum of inner turning angles in an optimal solution always equals pi. This implies that the problem can be solved by the standard ILP model without producing any integral subtours. Moreover, we give a simple constructive polynomial time algorithm to find such an optimal solution. If the number of vertices is even no such property holds.

Il seminario si svolgerà presso la sala riunioni della sez. di  Informatica e Automazione del Dipartimento di Ingegneria in via della Vasca Navale 79 a Roma (Google maps). Le  indicazioni per raggiungere il dipartimento sono disponibili al link:
http://www.inf.uniroma3.it/~atzeni/accesso/index.html

Per ulteriori informazioni rivolgersi a G. Nicosia (nicosia@ing.uniroma3.it, tel. 06 57333455).