# Sensitivity Analysis for Traveling Salesman

I am trying to understand how the idea of Sensitivity Analysis would apply to the Traveling Salesman Problem.

For instance, suppose my optimization algorithm returned the following path as the shortest path between 7 cities:

City 5, City 3, City 2, City 6, City 1, City 4, City 7

In the above case, how do we study the "Sensitivity Analysis" of this solution?

• If the objective function in this problem was differentiable, I could have taken the solution returned by the optimization solution and added some random noise to the solution - then, I could have seen how different the solutions with random noise were compared to the solutions without random noise. For example - suppose the solution returned was $$(x_1 = 2.1, x_2 = 13.4)$$, $$f(x_1,x_2) = 1.9 )$$. I could see how much $$f(x_1,x_2)$$ deviates from 1.9 for neighboring values of $$x_1$$ and $$x_2$$ (e.g. $$x_1 = 2.2$$, $$x_2 = 13.5$$).

• In the Traveling Salesman Problem, my guess would be that I can randomly change the order for some of the cities and see how much these random changes affect the existing solution? For example, if City 5, City 3, City 2, City 6, City 1, City 4, City 7 is the optimal solution (e.g. suppose this path is 641 KM) - I could try City 5, City 3, City 2, City 6, City 1, City 7, City 4 and see how much this new path measures (e.g. 712 KM).

Is this how "Sensitivity Analysis" is conducted for discrete combinatorial problems?

• Add noise to the distances, re-solve and compare the objective values Feb 3, 2022 at 6:55
• Sensitivity analysis is a concept that is usually applied only to continuous models. For discrete models there are very few tools apart from solving different scenarios. Feb 3, 2022 at 9:01