With what budget? P versus NP is our terrible rough estimate for budgeting things like compute time. If you think you have a known NP case where do you even start to plan a budget (for grant proposals if nothing else) on how much computing resources to "just throw at it"?
There is a good chance that the failure mode of the algorithm is to yield an invalid solution, not a suboptimal one, so in that case you do not even need to know the optimal solution. Besides that you are not going to find a counter example by generating random instances, you will be carefully constructing it with spacial properties to make the algorithm fail. Because of the special structure you might just be able to figure out the optimal solution in your head. And I would guess that you can construct a counter example with ten or so cities and you can easily brute force a few million or billion paths. If you need twenty cities however, things look already different but there are solvers that should still easily deal with those cases.
Comments
With what budget? P versus NP is our terrible rough estimate for budgeting things like compute time. If you think you have a known NP case where do you even start to plan a budget (for grant proposals if nothing else) on how much computing resources to "just throw at it"?
There is a good chance that the failure mode of the algorithm is to yield an invalid solution, not a suboptimal one, so in that case you do not even need to know the optimal solution. Besides that you are not going to find a counter example by generating random instances, you will be carefully constructing it with spacial properties to make the algorithm fail. Because of the special structure you might just be able to figure out the optimal solution in your head. And I would guess that you can construct a counter example with ten or so cities and you can easily brute force a few million or billion paths. If you need twenty cities however, things look already different but there are solvers that should still easily deal with those cases.