doi: 10.3934/fods.2022006
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

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

Received  January 2021 Revised  December 2021 Early access March 2022

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.

Citation: Erik Carlsson, John Gunnar Carlsson, Shannon Sweitzer. Applying topological data analysis to local search problems. Foundations of Data Science, doi: 10.3934/fods.2022006
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. KanungoD. M. MountN. S. NetanyahuC. D. PiatkoR. 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. KirkpatrickC. 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. VansteenwegenW. SouffriauG. 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. YiJ. Ahn and S. Ji, An effective optimization method for machine learning based on adam, Applied Sciences, 10 (2020), 1073.  doi: 10.3390/app10031073.

show all references

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. KanungoD. M. MountN. S. NetanyahuC. D. PiatkoR. 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. KirkpatrickC. 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. VansteenwegenW. SouffriauG. 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. YiJ. Ahn and S. Ji, An effective optimization method for machine learning based on adam, Applied Sciences, 10 (2020), 1073.  doi: 10.3390/app10031073.

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)
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
Figure 3.  Using higher order homology to obtain new local minimizers
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
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
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
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
Table 1.  The sequence of vertices in a representative cycle for the jeu de taquin game, generated by Javaplex [1]
[1]

Poonam Savsani, Mohamed A. Tawhid. Discrete heat transfer search for solving travelling salesman problem. Mathematical Foundations of Computing, 2018, 1 (3) : 265-280. doi: 10.3934/mfc.2018012

[2]

Felix X.-F. Ye, Yue Wang, Hong Qian. Stochastic dynamics: Markov chains and random transformations. Discrete and Continuous Dynamical Systems - B, 2016, 21 (7) : 2337-2361. doi: 10.3934/dcdsb.2016050

[3]

Yakov Pesin. On the work of Sarig on countable Markov chains and thermodynamic formalism. Journal of Modern Dynamics, 2014, 8 (1) : 1-14. doi: 10.3934/jmd.2014.8.1

[4]

Renato Bruni, Gianpiero Bianchi, Alessandra Reale. A combinatorial optimization approach to the selection of statistical units. Journal of Industrial and Management Optimization, 2016, 12 (2) : 515-527. doi: 10.3934/jimo.2016.12.515

[5]

L. Cioletti, E. Silva, M. Stadlbauer. Thermodynamic formalism for topological Markov chains on standard Borel spaces. Discrete and Continuous Dynamical Systems, 2019, 39 (11) : 6277-6298. doi: 10.3934/dcds.2019274

[6]

Karoline Disser, Matthias Liero. On gradient structures for Markov chains and the passage to Wasserstein gradient flows. Networks and Heterogeneous Media, 2015, 10 (2) : 233-253. doi: 10.3934/nhm.2015.10.233

[7]

Demetris Hadjiloucas. Stochastic matrix-valued cocycles and non-homogeneous Markov chains. Discrete and Continuous Dynamical Systems, 2007, 17 (4) : 731-738. doi: 10.3934/dcds.2007.17.731

[8]

Brian Marcus and Selim Tuncel. Powers of positive polynomials and codings of Markov chains onto Bernoulli shifts. Electronic Research Announcements, 1999, 5: 91-101.

[9]

Marcelo Sobottka. Right-permutative cellular automata on topological Markov chains. Discrete and Continuous Dynamical Systems, 2008, 20 (4) : 1095-1109. doi: 10.3934/dcds.2008.20.1095

[10]

Peter E. Kloeden, Victor Kozyakin. Asymptotic behaviour of random tridiagonal Markov chains in biological applications. Discrete and Continuous Dynamical Systems - B, 2013, 18 (2) : 453-465. doi: 10.3934/dcdsb.2013.18.453

[11]

Mark F. Demers, Christopher J. Ianzano, Philip Mayer, Peter Morfe, Elizabeth C. Yoo. Limiting distributions for countable state topological Markov chains with holes. Discrete and Continuous Dynamical Systems, 2017, 37 (1) : 105-130. doi: 10.3934/dcds.2017005

[12]

Jianjun Liu, Min Zeng, Yifan Ge, Changzhi Wu, Xiangyu Wang. Improved Cuckoo Search algorithm for numerical function optimization. Journal of Industrial and Management Optimization, 2020, 16 (1) : 103-115. doi: 10.3934/jimo.2018142

[13]

Simone Göttlich, Oliver Kolb, Sebastian Kühn. Optimization for a special class of traffic flow models: Combinatorial and continuous approaches. Networks and Heterogeneous Media, 2014, 9 (2) : 315-334. doi: 10.3934/nhm.2014.9.315

[14]

Alexander Pankov. Traveling waves in Fermi-Pasta-Ulam chains with nonlocal interaction. Discrete and Continuous Dynamical Systems - S, 2019, 12 (7) : 2097-2113. doi: 10.3934/dcdss.2019135

[15]

Nicolai Sætran, Antonella Zanna. Chains of rigid bodies and their numerical simulation by local frame methods. Journal of Computational Dynamics, 2019, 6 (2) : 409-427. doi: 10.3934/jcd.2019021

[16]

Kien Ming Ng, Trung Hieu Tran. A parallel water flow algorithm with local search for solving the quadratic assignment problem. Journal of Industrial and Management Optimization, 2019, 15 (1) : 235-259. doi: 10.3934/jimo.2018041

[17]

Behrouz Kheirfam, Morteza Moslemi. On the extension of an arc-search interior-point algorithm for semidefinite optimization. Numerical Algebra, Control and Optimization, 2018, 8 (2) : 261-275. doi: 10.3934/naco.2018015

[18]

Mohamed A. Tawhid, Ahmed F. Ali. An effective hybrid firefly algorithm with the cuckoo search for engineering optimization problems. Mathematical Foundations of Computing, 2018, 1 (4) : 349-368. doi: 10.3934/mfc.2018017

[19]

Tatsuaki Kimura, Hiroyuki Masuyama, Yutaka Takahashi. Light-tailed asymptotics of GI/G/1-type Markov chains. Journal of Industrial and Management Optimization, 2017, 13 (4) : 2093-2146. doi: 10.3934/jimo.2017033

[20]

Salah Eddine Choutri, Boualem Djehiche, Hamidou Tembine. Optimal control and zero-sum games for Markov chains of mean-field type. Mathematical Control and Related Fields, 2019, 9 (3) : 571-605. doi: 10.3934/mcrf.2019026

 Impact Factor: 

Metrics

  • PDF downloads (229)
  • HTML views (183)
  • Cited by (0)

[Back to Top]