Minimization and maximization versions of the quadratic travelling salesman problem

References

• Lawler EL, Lenstra JK, Rinnooy Kan AHG, et al. The traveling salesman problem: a guided tour of combinatorial optimization. Wiley-Interscience series in discrete mathematics and optimization. Chicester: John Wiley & Sons; 1985.
   Google Scholar
• Reinelt G. The traveling salesman: computational solutions for TSP applications. Berlin: Springer; 1994.
   Google Scholar
• Applegate DL, Bixby RE, Chvátal V, et al. The traveling salesman problem: a computational study. Princeton (NJ): Princeton University Press; 2006.
   Google Scholar
• Gutin G, Punnen AP, editors. The traveling salesman problem and its variations. Combinatorial optimization. Vol. 12. New York (NY): Springer; 2007.
   Google Scholar
• Aggarwal A, Coppersmith D, Khanna S, et al. The angular-metric traveling salesman problem. SIAM J Comput. 2000;29(3):697–711.
   Web of Science ®Google Scholar
• Amaldi E, Galbiati G, Maffioli F. On minimum reload cost paths, tours, and flows. Networks. 2011;57(3):254–260.
   Web of Science ®Google Scholar
• Fischer A, Helmberg C. The symmetric quadratic traveling salesman problem. Math Program A. 2013;142(1):205–254.
   Web of Science ®Google Scholar
• Jäger G, Molitor P. Algorithms and experimental study for the traveling salesman problem of second order. Proceedings of COCOA. Lecture notes in computer science. Vol. 5165. Berlin: Springer; 2008. p. 211–224.
   Google Scholar
• Fischer A, Fischer F, Jäger G, et al. Exact algorithms and heuristics for the quadratic traveling salesman problem with an application in bioinformatics. Disc Appl Math. 2014;166:97–114.
   Web of Science ®Google Scholar
• Fischer A, Fischer F, Jäger G, et al. Computational recognition of RNA splice sites by exact algorithms for the quadratic traveling salesman problem. Computation. 2015;3(2):285–298.
   Web of Science ®Google Scholar
• Fischer A, Fischer F. An extended approach for lifting clique tree inequalities. J Comb Optim. 2015;30(3):489–519. doi:10.1007/s10878-013-9647-3
   Web of Science ®Google Scholar
• Savla K, Frazzoli E, Bullo F. Traveling salesperson problems for the Dubins vehicle. IEEE Trans Autom Control. 2008;53(6):1378–1391.
   Web of Science ®Google Scholar
• Woods B, Punnen A, Stephen T. A linear time algorithm for the 3-neighbour traveling salesman problem on Halin graphs and extensions, 2015. Available from: arXiv:1504.02151.
   Google Scholar
• Fischer A. An analysis of the asymmetric quadratic traveling salesman polytope. SIAM J Disc Math. 2014;28(1):240–276.
   Web of Science ®Google Scholar
• Rostami B, Malucelli F, Belotti P, Gualandi S. Lower bounding procedure for the asymmetric quadratic traveling salesman problem. European J Oper Res. 2016;253:584–592.
   Web of Science ®Google Scholar
• Dumitrescu A, Pach J, Tóth G. Drawing Hamiltonian cycles with no large angles. Electron J Comb. 2012;19(2):P31.
   Web of Science ®Google Scholar
• Fekete SP, Woeginger GJ. Angle-restricted tours in the plane. Comput Geom. 1997;8(4):195–218.
   Web of Science ®Google Scholar
• Pferschy U, Staněk R. Generating subtour elimination constraints for the TSP from pure integer solutions. Central European J Oper Res. 2016. doi:10.1007/s10100-016-0437-8.
   PubMed Web of Science ®Google Scholar
• Dantzig G, Fulkerson R, Johnson S. Solution of a large-scale traveling-salesman problem. J Oper Res Soc Amer. 1954;2(4):393–410.
   Web of Science ®Google Scholar
• Galbiati G, Gualandi S, Maffioli F. On minimum reload cost cycle cover. Disc Appl Math. 2014;164(Part 1):112–120.
   Web of Science ®Google Scholar
• Dey SS, Molinaro M, Wang Q. How good are sparse cutting-planes? Proceedings of the 17th International Conference on Integer Programming and Combinatorial Optimization, IPCO. Lecture notes in computer science. Vol. 8494. Cham: Springer; 2014. p. 261–272.
   Google Scholar
• Fischer A. 2013. A polyhedral study of quadratic traveling salesman problems [PhD thesis]. Chemnitz University of Technology, Department of Mathematics. Available from: http://www.qucosa.de/fileadmin/data/qucosa/documents/11834/Dissertation_Anja_Fischer.pdf.
   Google Scholar
• Meier JF, Clausen U. Solving classical and new single allocation hub location problems on Euclidean data. Optimization Online. 2015. Available from: 2015–03-4816.
   Google Scholar
• Beardwood J, Halton JH, Hammersley JM. The shortest path through many points. Math Proc Cambridge Philos Soc. 1959;55(4):299–327.
   Google Scholar
• Hershberger J, Suri S. Applications of a semi-dynamic convex hull algorithm. BIT Numer Math. 1992;32(2):249–267.
   Web of Science ®Google Scholar
• Guibas LJ, Hershberger J, Snoeyink J. Compact interval trees: a data structure for convex hulls. Int J Comput Geom & Appl. 1991;1(1):1–22.
   Google Scholar
• Abellanas M, Garcia-Lopez J, Hernández-Peñalver G, et al. Bipartite embeddings of trees in the plane. Disc Appl Math. 1999;93(2–3):141–148.
   Web of Science ®Google Scholar
• Fischer A, Meier JF, Pferschy U, et al. Linear models and computational experiments for the quadratic TSP. Electron Notes Disc Math. 2016;55:97–100.
   Google Scholar