GNN-BASED META-OPTIMISATION OF QUADTREE GRANULARITY FOR TSP ON FRACTAL POINT SETS

ABSTRACT: The Traveling Salesman Problem remains a fundamental challenge in combinatorial optimization, with scalability representing the primary obstacle for large-scale real-world instances containing thousands of cities. This paper introduces a paradigm shift from direct neural solving to meta-optimization, proposing a Graph Neural Network architecture that learns to determine optimal granularity parameters for quadtree-based hierarchical decomposition. We establish a rigorous mathematical framework demonstrating that the optimal granularity parameter k follows a scaling law k = 𝛩(N^α) where α = (q - 1) / (p(D) + q - 1), with p(D) representing the local solver's complexity exponent as a function of the fractal dimension D of the point distribution, and q the merging exponent. The GNN meta-optimizer, trained on 3,000 synthetic fractal instances, achieves an R2 of 0.984 with theoretical optima and demonstrates robust performance across 70 real-world VLSI datasets ranging from 131 to 10,000 cities. Results confirm that the proposed approach yields sublinear growth in granularity with problem size, effectively controlling computational complexity and validating the fractal-aware nature of the meta-optimization framework.