A Polyhedral Study of the Quadratic Traveling Salesman Problem

Anja Fischer ()
Additional contact information
Anja Fischer: TU Dortmund

A chapter in Operations Research Proceedings 2014, 2016, pp 143-149 from Springer

Abstract: Abstract In this paper we summarize some of the results of the author’s Ph.D.-thesis. We consider an extension of the traveling salesman problem (TSP). Instead of each path of two nodes, an arc, the costs depend on each three nodes that are traversed in succession. As such a path of three nodes, a 2-arc, is present in a tour if the two corresponding arcs are contained in that tour, we speak of a quadratic traveling salesman problem (QTSP). This problem is motivated by an application in biology, special cases are the TSP with reload costs as well as the angular-metric TSP. Linearizing the quadratic objective function, we derive a linear integer programming formulation and present a polyhedral study of the associated polytope. This includes the dimension as well as three groups of facet-defining inequalities. Some are related to the Boolean quadric polytope and some forbid conflicting configurations. Furthermore, we describe approaches to strengthen valid inequalities of TSP in order to get stronger inequalities for QTSP.

Keywords: Travel Salesman Problem; Travel Salesman Problem; Hamiltonian Cycle; Valid Inequality; Separation Problem (search for similar items in EconPapers)
Date: 2016
References: Add references at CitEc
Citations: View citations in EconPapers (2)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:oprchp:978-3-319-28697-6_21

Ordering information: This item can be ordered from
http://www.springer.com/9783319286976

DOI: 10.1007/978-3-319-28697-6_21

Access Statistics for this chapter

More chapters in Operations Research Proceedings from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().