Polyedertheorie und Algorithmen für das Graphische Travelling-Salesman-Problem

• Applicant: Professor Dr. Gerhard Reinelt
• Subject Area: Mathematics
• Term: from 2005 to 2010
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 17239119

• Final Report Year: 2010

Final Report Abstract

Für den Entwurf und die Implementierung einer bestimmten leistungsfähigen Klasse von Algorithmen, den sogenannten Branch-and-Cut-Verfahren, zur Lösung eines kombinatorischen Optimierungsproblems ist die Erforschung der Struktur zugeordneter Polyeder von Bedeutung. Das Projekt hat sich in diesem Kontext mit dem Graphischen Travelling-Salesman-Problem (GTSP) beschäftigt. Das GTSP unterscheidet sich von bekannten Travelling-Salesman-Problem dadurch, dass nicht alle direkten Verbindung zwischen Städten vorhanden sind, und so zum Besuch aller Städte sowohl Verbindungen mehrfach benutzt als auch Städte mehrfach besucht werden können bzw. müssen. Im Projekt wurden neue Kenntnisse über die Struktur von GTSP-Polyedern erworben und Software zur Unterstützung der Forschung durch automatisierte Berechnungen speziell für dieses Problem wurde erstellt.

Publications

• On the Graphical Relaxation of the Symmetric Thiveling Salesman Problem. Universite Libre de Bruxelles, Brussels, Belgium, 2006
  D.O. Theis
  
• Results on the Graphical Relaxation of the Symmetric TSP. International Symposium on Mathematical Programming, Rio de Janeiro, Brasilien, 2006
  D.O. Theis
  
• A global geometric approach to relaxations. Conference internationale en Combinatoire, Geometrie et Informatique théoretique CIRM, Marseille, Frankreich, 2007
  D.O. Theis
  
• Geometry of metrics embeddable in the real line. British Combinatorial Conference, Reading, UK, 2007
  D.O. Theis
  
• On convex sets associated with certain metrics and permutations. Department of Pure Mathematics and Computer Algebra, Ghent University, Ghent, Belgien, 2007
  D.O. Theis
  
• On the graphical relaxation of the symmetric traveling salesman polytope. Mathematical Programming - Series B 110(1) (2007), 175-193
  M. Oswald, G. Reinelt, D.O. Theis
  
• Local cuts revisited. Operations Research Letters 36(4), 2008, 430-433
  C. Buchheim, F. Liers and M. Oswald
  
• Odd minimum cut sets and b-matchings revisited. SIAM J. Discrete Math. 22:4 (2008), 1480-1487
  A.N. Letchford, G. Reinelt and D.O. Theis
  
• A branch-and-cut solver for the maximum stable set problem. J. Comb. Opt (2009)
  S. Rebennack, M. Oswald, D.O. Theis, H. Seitz, G. Reinelt and P.M. Pardalos
  (See online at https://doi.org/10.1007/s10878-009-9264-3)
• Applying mod-k-cuts for solving linear ordering problems. TOP 17(1) (2009), 158-170
  M. Oswald, G. Reinelt and H. Seitz
  
• Computations of GTSP-polyhedra. International Symposium on Mathematical Programming, Chicago, USA, 2009
  M. Oswald