Edge-wise Topological Divergence Gaps: Guiding Search in Combinatorial Optimization
By: Ilya Trofimov , Daria Voronkova , Alexander Mironenko and more
Potential Business Impact:
Finds shortest routes faster using shape math.
We introduce a topological feedback mechanism for the Travelling Salesman Problem (TSP) by analyzing the divergence between a tour and the minimum spanning tree (MST). Our key contribution is a canonical decomposition theorem that expresses the tour-MST gap as edge-wise topology-divergence gaps from the RTD-Lite barcode. Based on this, we develop a topological guidance for 2-opt and 3-opt heuristics that increases their performance. We carry out experiments with fine-optimization of tours obtained from heatmap-based methods, TSPLIB, and random instances. Experiments demonstrate the topology-guided optimization results in better performance and faster convergence in many cases.
Similar Papers
TSP integrality gap via 2-edge-connected multisubgraph problem under coincident IP optima
Optimization and Control
Finds best routes for delivery trucks.
TSP integrality gap via 2-edge-connected multisubgraph problem under coincident IP optima
Optimization and Control
Finds shortest routes for delivery trucks.
Generative Modeling for Robust Deep Reinforcement Learning on the Traveling Salesman Problem
Machine Learning (CS)
Helps delivery trucks find best routes faster.