Heuristic Acquisition for Data Science

Excerpt

The Traveling Salesman Problem (TSP) was first formulated in 1930 and is one of the most studied problems in optimization. If the optimal solution to the TSP can be found in polynomial time, it would then follow that every NP-hard problem could be solved in polynomial time, proving P = NP. We demonstrated an algorithm, which finds P ~ NP with scale, Rubin et al. 2016, 2018. Using a δ − ε proof, it is straightforward to show that as the number of cities goes to infinity, P goes to NP (i.e., δ > 0). This was demonstrated using a quadratic number of parallel processors because that speedup, by definition, is polynomial. A fastest parallel algorithm was defined. Using an arbitrary run of 5000 cities, we obtained a tour within 0.00001063% of the optimal using 4,166,667 virtual processors (Intel Xenon E5–1603 @ 2.8 GHz). To save the calculated extra 209 miles would take a quantum computer over (5000!/(2**4978 * 22!)) * 267,782 centuries. Clearly, the automated acquisition of heuristics and the associated P ~ NP solutions are an important problem warranting attention. Machine learning through self-randomization was demonstrated in the solution of the TSP. …