nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

Simulated Annealing Approach to Verify Vertex Adjacencies in the Traveling Salesperson Polytope

verfasst von : Anna Kozlova, Andrei Nikolaev

Erschienen in: Mathematical Optimization Theory and Operations Research

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

We consider 1-skeletons of the symmetric and asymmetric traveling salesperson polytopes whose vertices are all possible Hamiltonian tours in the complete directed or undirected graph, and the edges are geometric edges or one-dimensional faces of the polytope. It is known that the question whether two vertices of the symmetric or asymmetric traveling salesperson polytopes are nonadjacent is NP-complete. A sufficient condition for nonadjacency can be formulated as a combinatorial problem: if from the edges of two Hamiltonian tours we can construct two complementary Hamiltonian tours, then the corresponding vertices of the traveling salesperson polytope are not adjacent. We consider a heuristic simulated annealing approach to solve this problem. It is based on finding a vertex-disjoint cycle cover and a perfect matching. The algorithm has a one-sided error: the answer “not adjacent” is always correct, and was tested on random and pyramidal Hamiltonian tours.

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

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

Vorheriges Kapitel Pareto-Based Hybrid Algorithms for the Bicriteria Asymmetric Travelling Salesman Problem

Nächstes Kapitel Less Is More: Tabu Search for Bipartite Quadratic Programming Problem

Ageev, A.A., Pyatkin, A.V.: A 2-approximation algorithm for the metric 2-peripatetic salesman problem. In: Kaklamanis, C., Skutella, M. (eds.) WAOA 2007. LNCS, vol. 4927, pp. 103–115. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-77918-6_9CrossRefMATH

Aguilera, N.E., Katz, R.D., Tolomei, P.B.: Vertex adjacencies in the set covering polyhedron. Discrete Appl. Math. 218, 40–56 (2017). https://doi.org/10.1016/j.dam.2016.10.024MathSciNetCrossRefMATH

Arthanari, T.S.: On pedigree polytopes and Hamiltonian cycles. Discrete Math. 306(14), 1474–1492 (2006). https://doi.org/10.1016/j.disc.2005.11.030MathSciNetCrossRefMATH

Balinski, M.L.: Signature methods for the assignment problem. Oper. Res. 33(3), 527–536 (1985). https://doi.org/10.1287/opre.33.3.527MathSciNetCrossRefMATH

Baburin, A.E., Della Croce, F., Gimadi, E.K., Glazkov, Y.V., Paschos, V.Th.: Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2. Discrete Appl. Math. 157, 1988–1992 (2009). https://doi.org/10.1016/j.dam.2008.06.025MathSciNetCrossRef

Bondarenko, V.A.: Nonpolynomial lower bounds for the complexity of the traveling salesman problem in a class of algorithms. Autom. Rem. Contr. 44, 1137–1142 (1983)MathSciNetMATH

Bondarenko, V.A., Maksimenko, A.N.: Geometricheskie konstruktsii i slozhnost’ v kombinatornoy optimizatsii (Geometric constructions and complexity in combinatorial optimization), LKI, Moscow (2008). (in Russian)

Bondarenko, V.A., Nikolaev, A.V.: On graphs of the cone decompositions for the min-cut and max-cut problems. Int. J. Math. Sci. 2016 (2016). Article ID 7863650, 6 p. https://doi.org/10.1155/2016/7863650MathSciNetCrossRef

Bondarenko, V.A., Nikolaev, A.V.: Some properties of the skeleton of the pyramidal tours polytope. Electron. Notes Discrete Math. 61, 131–137 (2017). https://doi.org/10.1016/j.endm.2017.06.030CrossRefMATH

10.

Bondarenko, V.A., Nikolaev, A.V.: On the skeleton of the polytope of pyramidal tours. J. Appl. Ind. Math. 12, 9–18 (2018). https://doi.org/10.1134/S1990478918010027MathSciNetCrossRefMATH

11.

Chegireddy, C.R., Hamacher, H.W.: Algorithms for finding K-best perfect matchings. Discrete Appl. Math. 18, 155–165 (1987). https://doi.org/10.1016/0166-218X(87)90017-5MathSciNetCrossRefMATH

12.

Christof, T., Reinelt, G.: Decomposition and parallelization techniques for enumerating the facets of combinatorial polytopes. Int. J. Comput. Geom. Appl. 11, 423–437 (2001). https://doi.org/10.1142/S0218195901000560MathSciNetCrossRefMATH

13.

Combarro, E.F., Miranda, P.: Adjacency on the order polytope with applications to the theory of fuzzy measures. Fuzzy Set. Syst. 161, 619–641 (2010). https://doi.org/10.1016/j.fss.2009.05.004MathSciNetCrossRefMATH

14.

De Kort, J.B.J.M.: Bounds for the symmetric 2-peripatetic salesman problem. Optim. 23, 357–367 (1992). https://doi.org/10.1080/02331939208843770MathSciNetCrossRefMATH

15.

Edmonds, J.: Paths, trees, and flowers. Can. J. Math. 17, 449–467 (1965). https://doi.org/10.4153/CJM-1965-045-4MathSciNetCrossRefMATH

16.

Fiorini, S., Massar, S., Pokutta, S., Tiwary, H.R., De Wolf, R.: Exponential lower bounds for polytopes in combinatorial optimization. J. ACM 62 (2015). Article No. 17. https://doi.org/10.1145/2716307MathSciNetCrossRef

17.

Gabow, H.N.: Two algorithms for generating weighted spanning trees in order. SIAM J. Comput. 6, 139–150 (1977). https://doi.org/10.1137/0206011MathSciNetCrossRefMATH

18.

Glebov, A.N., Zambalaeva, D.Z.: A polynomial algorithm with approximation ratio 7/9 for the maximum two peripatetic salesmen problem. J. Appl. Ind. Math. 6, 69–89 (2012). https://doi.org/10.1134/S1990478912010085MathSciNetCrossRef

19.

Grötschel, M., Padberg, M.: Polyhedral theory. In: Lawler, E., Lenstra, J.K., Rinnooy Kan, A., Shmoys, D. (eds.) The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, pp. 251–305. Wiley, Chichester (1985)

20.

Hopcroft, J.E., Karp, R.M.: An \(n^{5/2}\) algorithm for maximum matchings in bipartite graphs. SIAM J. Comp. 2(4), 225–231 (1973). https://doi.org/10.1137/0202019MathSciNetCrossRefMATH

21.

Kirkpatrick, S., Gelatt, C.D., Vecchi, M.P.: Optimization by simulated annealing. Science 220(4598), 671–680 (1983). https://doi.org/10.1126/science.220.4598.671MathSciNetCrossRefMATH

22.

Kozlova, A.P., Nikolaev, A.V.: Proverka smezhnosti vershin mnogogrannika zadachi kommivoyazhyora (Verification of vertex adjacency in the traveling salesperson polytope). Zametki po informatike i matematike (Notes on Computer Science and Mathematics) 10, 51–58 (2018). (in Russian)

23.

Kühn, D., Osthus, D.: Hamilton decompositions of regular expanders: a proof of Kelly’s conjecture for large tournaments. Adv. Math. 237, 62–146 (2013). https://doi.org/10.1016/j.aim.2013.01.005MathSciNetCrossRefMATH

24.

Micali, S., Vazirani, V.V.: An \(O({\sqrt{|V|}}\cdot |E|)\) algorithm for finding maximum matching in general graphs. In: Proceedings of the 21st IEEE Symposium on Foundations of Computer Science, pp. 17–27 (1980). https://doi.org/10.1109/SFCS.1980.12

25.

Padberg, M.W., Rao, M.R.: The travelling salesman problem and a class of polyhedra of diameter two. Math. Program. 7(1), 32–45 (1974). https://doi.org/10.1007/BF01585502MathSciNetCrossRefMATH

26.

Papadimitriou, C.H.: The adjacency relation on the traveling salesman polytope is NP-Complete. Math. Program. 14, 312–324 (1978). https://doi.org/10.1007/BF01588973MathSciNetCrossRefMATH

27.

Rao, M.R.: Adjacency of the traveling salesman tours and 0-1 vertices. SIAM J. Appl. Math. 30, 191–198 (1976). https://doi.org/10.1137/0130021MathSciNetCrossRefMATH

28.

Rispoli, F.J., Cosares, S.: A bound of \(4\) for the diameter of the symmetric traveling salesman polytope. SIAM J. Discrete Math. 11(3), 373–380 (1998). https://doi.org/10.1137/S0895480196312462MathSciNetCrossRefMATH

29.

Sierksma, G.: The skeleton of the symmetric traveling salesman polytope. Discrete Appl. Math. 43, 63–74 (1993). https://doi.org/10.1016/0166-218X(93)90169-OMathSciNetCrossRefMATH

30.

Tutte, W.T.: A short proof of the factor theorem for finite graphs. Can. J. Math. 6, 347–352 (1954). https://doi.org/10.4153/CJM-1954-033-3MathSciNetCrossRefMATH

Titel: Simulated Annealing Approach to Verify Vertex Adjacencies in the Traveling Salesperson Polytope
verfasst von: Anna Kozlova
Andrei Nikolaev
Verlag: Springer International Publishing
Buch: Mathematical Optimization Theory and Operations Research
Print ISBN: 978-3-030-22628-2

Electronic ISBN: 978-3-030-22629-9

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-030-22629-9_26

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 "Technik"

Springer Professional "Wirtschaft"