NP-hard combinatorial optimization problems are the family of integer constrained optimization problems which are intractable to solve optimally at large scales.
Robust approximation algorithms to popular problems have immense practical applications and are the backbone of modern industries.
Among combinatorial problems, the 2D Euclidean Travelling Salesman Problem (TSP) has been the most intensely studied NP-hard graph problem in the Operations Research (OR) community, with applications in logistics, genetics and scheduling [1]}.
TSP is intractable to solve optimally above thousands of nodes for modern computers [2]}.
In practice, the Concorde TSP solver [3]}
uses linear programming with carefully handcrafted heuristics to find solutions up to tens of thousands of nodes, but with prohibitive execution times.The largest TSP solved by Concorde to date has 109,399 nodes with a total running time of 7.5 months.
Besides, the development of problem-specific OR solvers such as Concorde for novel or under-studied problems arising in scientific discovery [4]}, [5]} or computer architecture [6]}, [7]} requires significant time and specialized knowledge.
