nach oben

Journal of Combinatorial Optimization

Erschienen in:

01.10.2015

An extended approach for lifting clique tree inequalities

verfasst von: Anja Fischer, Frank Fischer

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 3/2015

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We present a new lifting approach for strengthening arbitrary clique tree inequalities that are known to be facet defining for the symmetric traveling salesman problem in order to get stronger valid inequalities for the symmetric quadratic traveling salesman problem (SQTSP). Applying this new approach to the subtour elimination constraints (SEC) leads to two new classes of facet defining inequalities of SQTSP. For the special case of the SEC with two nodes we derive all known conflicting edges inequalities for SQTSP. Furthermore we extend the presented approach to the asymmetric quadratic traveling salesman problem (AQTSP).

Vorheriger Artikel Four edge-grafting theorems on the reciprocal degree distance of graphs and their applications

Nächster Artikel Scheduling with task replication on desktop grids: theoretical and experimental analysis

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Nur mit Berechtigung zugänglich

Aggarwal A, Coppersmith D, Khanna S, Motwani R, Schieber B (1999) The angular-metric traveling salesman problem. SIAM J Comput 29:697–711MathSciNetCrossRef

Amaldi E, Galbiati G, Maffioli F (2011) On minimum reload cost paths, tours, and flows. Networks 57:254–260

Dantzig G, Fulkerson R, Johnson S (1954) Solution of a large-scale traveling-salesman problem. Oper Res 2:393–410MathSciNet

Edmonds J (1965) Maximum matching and a polyhedron with \(0,1\) vertices. J Res Nat Bureau Stand 69 B:125–130MathSciNetCrossRef

Fischer A (2011) The asymmetric quadratic traveling salesman problem. Preprint 2011–2019, Fakultät für Mathematik, Technische Universität Chemnitz, D-09107 Chemnitz, Germany

Fischer A, Helmberg C (2012) The symmetric quadratic traveling salesman problem. Math Program 1–50

Fischetti M (1995) Clique tree inequalities define facets of the asymmetric traveling salesman polytope. Discret Appl Math 56(1):9–18MathSciNetCrossRef

Grötschel M, Padberg MW (1977) Lineare Charakterisierungen von Travelling Salesman Problemen. Zeitschrift für Oper Res Ser A 21(1):33–64

Grötschel M, Padberg MW (1979a) On the symmetric travelling salesman problem I: inequalities. Math Program 16:265–280CrossRef

Grötschel M, Padberg MW (1979b) On the symmetric travelling salesman problem II: lifting theorems and facets. Math Program 16:281–302CrossRef

Grötschel M, Padberg MW (1985) Polyhedral theory. In: Lawler EL, Lenstra JK, Kan AHGR, Shmoys DB (Eds) The traveling salesman problem. A guided tour of combinatorial optimization, chap 8, pp 251–306

Grötschel M, Pulleyblank WR (1986) Clique tree inequalities and the symmetric travelling salesman problem. Math Oper Res 11(4):537–569MathSciNetCrossRefMATH

Jäger G, Molitor P (2008) Algorithms and experimental study for the traveling salesman problem of second order. Lecture notes in computer science vol 5165. Springer, Berlin pp 211–224

Titel: An extended approach for lifting clique tree inequalities
verfasst von: Anja Fischer
Frank Fischer
Publikationsdatum: 01.10.2015
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 3/2015
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-013-9647-3

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 3/2015

-labelling of the direct product of a complete graph and a cycle

Online traveling salesman problem with deadlines and service flexibility

Some results on the reciprocal sum-degree distance of graphs

An efficient meta-heuristic algorithm for grid computing

The game Grundy indices of graphs

Rank bounds for a hierarchy of Lovász and Schrijver