Is there a known (polynomial in number of nodes) algorithm to generate TSP instances with known optimal value?
The idea is to be able to generating arbitrary large instances with known optimal value, in order to be able to test heuristics on them.
I found the paper Arthur, J. & Frendeway, J. Generating Travelling-Salesman Problems with Known Optimal Tours, The Journal of the Operational Research Society, Vol. 39, No. 2 (Feb., 1988), pp. 153-159 for generating TSP with known optimal, alas I cannot access it.