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

• Antragsteller: Professor Dr. Gerhard Reinelt
• Fachliche Zuordnung: Mathematik
• Förderung: Förderung von 2005 bis 2010
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 17239119

• Erstellungsjahr: 2010

Zusammenfassung der Projektergebnisse

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.

Projektbezogene Publikationen (Auswahl)

• 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
  
• 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