I can't immediately think of a reduction that would factor this in so the best thing may be to just reduce this to the appropriate ILP instance and use a mixed ILP approximator like GLPK (or Gurobi is free for students too).

Incidentally, achieving a polynomially-sized ILP formulation for TSP isn't quite obvious. Wikipedia has a good explanation of how to do this: https://en.wikipedia.org/wiki/Travelling_salesman_problem#In.... I'm not sure if the metric TSP has a simpler formulation.

Edit: Now that I think about it, it may be difficult to express the constraint that edges should be balanced out in a linear way. I happened to write about a similar problem a while ago (https://modalduality.org/posts/optimizing-color-coding/), I ended up giving up on finding a linear formulation and went for sequential least squares instead.

I am saying you may map K1 as √((x1-x2)^2+(y1-y2)^2) to find least distance, but TSP allows for arbitrary constants. So remove the √ and long trips will be strongly avoided.

PS: As far as I know you can use any arbitrary set of constants then use a linear solver. Or am I forgetting about something?

You might make your weight function as w(d, p) = d * (2 ^ p)

Note that the licensing terms do restrict its free use to "academic research."

Then it is not "open source" (violates "No Discrimination Against Fields of Endeavor") nor is it free software (violates the freedom to use for any purpose). It's proprietary -- just because the source code is available doesn't make something "open source" nor does it make it free software.

In own research (inverse problems related to signal recovery), I've noticed that a lot of NP-hard problems are actually easily solvable given that the data has some kind of structure to it. I know very little about computational complexity theory, but I've read some papers describing how there is often a phase transition where a high SNR puts the problem in P territory, but a sufficiently low SNR moves the problem moves to NP territory (but it's still solvable). Beyond the phase transition, a solution is information theoretically impossible. I wonder if most of these real world TSP problems actually lie in P, but I don't know how one would go about showing that. (I haven't performed a literature search, but I wouldn't be surprised if someone has already demonstrated this.)

It would be, if you'd want to do a speedrun, though.

With that many points, how do you prove that your solution is optimal?

An easy example is by using duality when solving linear programs.

And sometimes your upper bound is close enough to what you already have so you can just say something like "well my solution gets 190 points, I have an upper bound of 190.5 points, and all point rewards are integral so I must have the optimal solution."

This is easy to understand with integer factorization: It is very hard to factor large integers. Yet, if I where to give you two numbers, it is very easy to verify that their product is the integer you where looking at. So factorization is easy to verify, but hard to do (side-note: This is an intentional illustrative simplification. Integer factorization is not known to actually be "hard" and it is not known whether "hard" is even a thing. See below).

And that's the definition of an NP problem: It has a polynomial time deterministic algorithm to verify a solution.

An NP-complete problem is a problem that is at least as hard as any NP problem. That is, if you have an algorithm for an NP-complete problem, you can take any NP problem, transform it efficiently into that problem, use your algorithm and transform the solution efficiently back. Thus, if you've solved an NP-complete problem efficiently, you can solve all NP problems efficiently. TSP is NP-complete. Whether or not Integer Factorization is NP-complete is unknown.

Lastly, there is the question of whether there are problems that are in NP (that is, have a polynomial algorithm to verify a solution) but not in P (that is, have a polynomial algorithm to find a solution). That's the famous P vs. NP question, which is currently undecided.