Applying topological data analysis to local search problems

Erik Carlsson; John Gunnar Carlsson; Shannon Sweitzer

doi:10.3934/fods.2022006

Article Contents

2022, Volume 4, Issue 4: 563-579. Doi: 10.3934/fods.2022006

This issue Previous Article Reconstructing linearly embedded graphs: A first step to stratified space learning Next Article The (homological) persistence of gerrymandering

Applying topological data analysis to local search problems

1.
Department of Mathematics, UC Davis, USA
2.
Department of Industrial and Systems Engineering, University of Southern California, USA

^* Corresponding author: John Gunnar Carlsson
^* Corresponding author: John Gunnar Carlsson

Received: January 2021

Revised: December 2021

Early access: March 2022

Published: December 2022

Abstract / Introduction Full Text(HTML) Figure(7) / Table(1) Related Papers Cited by

Abstract

We present an application of topological data analysis (TDA) to discrete optimization problems, which we show can improve the performance of the 2-opt local search method for the traveling salesman problem by simply applying standard Vietoris-Rips construction to a data set of trials. We then construct a simplicial complex which is specialized for this sort of simulated data set, determined by a stochastic matrix with a steady state vector $ (P,\pi) $. When $ P $ is induced from a random walk on a finite metric space, this complex exhibits similarities with standard constructions such as Vietoris-Rips on the data set, but is not sensitive to outliers, as sparsity is a natural feature of the construction. We interpret the persistent homology groups in several examples coming from random walks and discrete optimization, and illustrate how higher dimensional Betti numbers can be used to classify connected components, i.e. zero dimensional features in higher dimensions.

Keywords:

Mathematics Subject Classification: 55N31, 60J10, 90C27.

Citation:

Full Text(HTML)

Figure 1. A 2-opt exchange on a tour of $ 8 $ points. The edges $ (3,7) $ and $ (4,5) $ in (1a) are replaced with $ (3,4) $ and $ (7,5) $ in (1b)

Download: Full-size image PowerPoint slide

Figure 2. The ratio of objective values obtained with and without TDA on the 41 TSPLIB benchmark instances; the horizontal position corresponds to alphabetical order of the name of the instance. Ratios less than $ 1 $ are marked with a circle, indicating that TDA-assisted search is superior. Ratios greater than 1 are marked with a diamond, indicating that TDA-assisted search is inferior. Ratios equal to 1 are marked with a square, indicating that the two methods result in the same objective value. The average ratio over all 42 instances is marked with a dashed line

Download: Full-size image PowerPoint slide

Figure 3. Using higher order homology to obtain new local minimizers

Download: Full-size image PowerPoint slide

Figure 4. The "best-so-far" objective values reported for the $ k $-means example from Figure 3, with $ k=3 $ and $ n=1000 $; local search does not improve between iterations 39 and 250, at which point we begin seeding using convex combinations of the representative $ \beta_{1} $ cycle as described. Using seeding of this kind rapidly leads to several new local minimizers between iterations 250 and 300

Download: Full-size image PowerPoint slide

Figure 5. The barcode diagrams for Construction 1 applied to the "jeu de taquin" Markov chain. The 100 longest bars are shown. Despite having many shorter ones, one can see three lasting bars in the $ \beta_1 $ diagram

Download: Full-size image PowerPoint slide

Figure 6. barcode diagrams built from the data set in Figure 6a. Figure 6b shows the results of applying Vietoris-Rips, which shows some $ \beta_1 $ features reflecting the two voids in the data set. Figures 6c and 6d are built using a random walk, and show more distinguishable features, because outliers produce high persistence values

Download: Full-size image PowerPoint slide

Figure 7. A Beale function $ F(x,y) $ on a region shown in 7a, then modeled on a $ 35\times 35 $ grid. There are 4 types of path $ \varphi(x) $ with low values of $ F(x,\varphi(x)) $, upper left/lower left through upper right/lower right. The values of $ f(p) $ on $ 0 $-simplices $ p\in X $ for the complex from Section 3.3 are shown with $ m\in \{1,...,k\} $, for various values of $ k $. Notice that the diagram for $ k=8 $ is already quite similar to the $ k=\infty $ case, which is the default in Construction 1. The major bars for the relative first Betti numbers correspond to the four paths in 7f. Notice there is a second bar in 7e corresponding to two dense regions

Download: Full-size image PowerPoint slide

Table 1. The sequence of vertices in a representative cycle for the jeu de taquin game, generated by Javaplex [1]

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	H. Adams, A. Tausz and M. Vejdemo-Johansson, JavaPlex: A research software package for persistent (co) homology, In International Congress on Mathematical Software, Springer, 2014, 129–136. doi: 10.1007/978-3-662-44199-2_23.
[2]	D. Aldous and J. A. Fill, Reversible markov chains and random walks on graphs, Unfinished monograph, recompiled 2014, 2002. available at http://www.stat.berkeley.edu/$\sim$aldous/RWG/book.html.
[3]	E. M. L. Beale and J. Forrest, Global optimization using special ordered sets, Mathematical Programming, 10 (1976), 52-69. doi: 10.1007/BF01580653.
[4]	P. Bendich, T. Galkovskyi and J. Harer, Improving homology estimates with random walks, Inverse Problems, 27 (2011), 124002, 14pp. doi: 10.1088/0266-5611/27/12/124002.
[5]	E. Carlsson and J. Carlsson, A new construction for sublevel set persistence, 2021.
[6]	E. Carlsson and J. Carlsson, Topology and local optima in computer vision, SN Computer Science, 3 (2022), Article number: 138. doi: 10.1007/s42979-021-01003-x.
[7]	R. Chelouah and P. Siarry, Tabu search applied to global optimization, European Journal of Operational Research, 123 (2000), 256-270. doi: 10.1016/S0377-2217(99)00255-6.
[8]	C. Chen, X. Ni, Q. Bai and Y. Wang, A topological regularizer for classifiers via persistent homology, In The 22nd International Conference on Artificial Intelligence and Statistics, PMLR, 2019, 2573–2582.
[9]	F. Chung and S.-T. Yau, Discrete green's functions, Journal of Combinatorial Theory, Series A, 91 (2000), 191-214. doi: 10.1006/jcta.2000.3094.
[10]	F. R. Cohen, On configuration spaces, their homology, and lie algebras, Journal of Pure and Applied Algebra, 100 (1995), 19-42. doi: 10.1016/0022-4049(95)00054-Z.
[11]	P. Corcoran and B. Deng, Regularization of persistent homology gradient computation, arXiv preprint, arXiv: 2011.05804, 2020.
[12]	K. A. Dowsland and J. Thompson, Simulated annealing, Handbook of Natural Computing, 2012, 1623–1655.
[13]	H. Edelsbrunner and J. Harer, Computational Topology - an Introduction, American Mathematical Society, 2010. doi: 10.1090/mbk/069.
[14]	M. Gendreau and J. -Y. Potvin, Tabu search, Handbook of Metaheuristics, 37–55, Internat. Ser. Oper. Res. Management Sci., 272, Springer, Cham, 2019.
[15]	R. Ghrist and S. Krishnan, A topological max-flow-min-cut theorem, In 2013 IEEE Global Conference on Signal and Information Processing, IEEE, 2013, 815–818. doi: 10.1109/GlobalSIP. 2013.6737016.
[16]	F. Glover and M. Laguna, Tabu search, Handbook of Combinatorial Optimization, 3 (1998), 621-757.
[17]	G. Hamerly and J. Drake, Accelerating Lloyd's algorithm for k-means clustering, In Partitional Clustering Algorithms, 2015, 41–78. doi: 10.1007/978-3-319-09259-1_2.
[18]	K. Helsgaun, General k-opt submoves for the lin–kernighan tsp heuristic, Mathematical Programming Computation, 1 (2009), 119-163. doi: 10.1007/s12532-009-0004-6.
[19]	T. Kanungo, D. M. Mount, N. S. Netanyahu, C. D. Piatko, R. Silverman and A. Y. Wu, An efficient k-means clustering algorithm: Analysis and implementation, IEEE Transactions on Pattern Analysis and Machine Intelligence, 24 (2002), 881-892. doi: 10.1109/TPAMI.2002.1017616.
[20]	P. Kilby, P. Prosser and P. Shaw, Guided local search for the vehicle routing problem with time windows, In Meta-Heuristics, 1999, 473–486. doi: 10.1007/978-1-4615-5775-3_32.
[21]	S. Kirkpatrick, C. D. Gelatt and M. P. Vecchi, Optimization by simulated annealing, science, 220 (1983), 671-680. doi: 10.1126/science.220.4598.671.
[22]	A. Nigmetov, A. S. Krishnapriyan, N. Sanderson and D. Morozov, Topological regularization via persistence-sensitive optimization, arXiv preprint, arXiv: 2011.05290, 2020.
[23]	G. Reinelt, Tsplib - a traveling salesman problem library, ORSA Journal on Computing, 3 (1991), 376-384. doi: 10.1287/ijoc.3.4.376.
[24]	T. Stützle, Iterated local search for the quadratic assignment problem, European Journal of Operational Research, 174 (2006), 1519-1539. doi: 10.1016/j.ejor.2005.01.066.
[25]	P. Vansteenwegen, W. Souffriau, G. V. Berghe and D. Van Oudheusden, A guided local search metaheuristic for the team orienteering problem, European Journal of Operational Research, 196 (2009), 118-127.
[26]	M. Vejdemo-Johansson and P. Skraba, Topology, big data and optimization, Big Data Optimization: Recent Developments and Challenges, 18 (2016), 147-176.
[27]	C. Voudouris and E. Tsang, Guided local search and its application to the traveling salesman problem, European Journal of Operational Research, 113 (1999), 469-499. doi: 10.1016/S0377-2217(98)00099-X.
[28]	D. Yi, J. Ahn and S. Ji, An effective optimization method for machine learning based on adam, Applied Sciences, 10 (2020), 1073. doi: 10.3390/app10031073.