Séminaire: «TSP Reloaded - Solution Approaches for the Quadratic Traveling Salesman Problem»

Séminaire en optimisation GERAD/CRC-ONDI

The traveling salesman problem (TSP) is one of the most extensively studied combinatorial optimization problems. The quadratic traveling salesman problem (QTSP) differs from the TSP in that the costs do not depend on two successive nodes but on three successive nodes that are visited in succession in a tour.  The task is to find a tour of minimum total cost. Originally motivated by an application in biology, the QTSP includes as special cases the angular-metric TSP used in robotics and the TSP with reload costs used in the planning of telecommunication and freight networks.

In the talk we present solution approaches for the QTSP. The main approach is based on a linearized integer programming formulation that can be improved by several facet-defining classes of inequalities. Most of the facets can be derived by using general strengthening approaches that allow to lift valid inequalities for the TSP to improved inequalities for QTSP. Additionally, the complexity of the corresponding separation problems is investigated.. Finally we demonstrate the usefulness of the new cuts. Real world instances from biology can be solved for up to 100 nodes in about ten minutes. Randomly generated instances turn out to be difficult, but for these semidefinite relaxations improved by the cutting planes help to reduce the gap at the root node significantly.

---------------------------------------
Important
Ce séminaire vous permettra d'échanger avec le conférencier et les chercheurs présents autour de boissons et de collations.
Nous vous remercions de confirmer votre présence (http://doodle.com/gt6tpdpu5spsb4kv).