I been looking at this site and it says that people found solutions for TSP tours that are just 0.031% higher than the optimal tour is. Without finding the optimal tour how does they know what length it is supposed to be?
How can you bound the error of an approximation without knowing the optimal solution?
complexity theory;approximation
In general when you want to bound the approximation ratio of an algorithm you look for an easy lower bound on the optimal value. The most straightforward is often the LP relaxation of a (suitably chosen) ILP formulation of the problem. Sometimes other things are used, for TSP for example you can also use the weight of a MST (the optimal tour minus one edge is a tree, so it can't weigh less than the MST).For particular instances you can of course still use the thing you use in your proofs, i.e. you can solve the LP and compare your heuristic solution to the LP value. If you have more CPU time on your hands you can also start a branch-and-bound process to solve the ILP. Even if you don't solve the ILP completely, you get better lower bounds from LP duality.