Sensitivity Analysis for Traveling Salesman

Question

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?

Answer 1

You can certainly do sensitivity/parametric analysis on the objective function. If you are interested in the effect of changing a single coefficient in a linear objective function to be minimized, e.g. as in the TSP, then a general result is that the optimal objective value is a concave function (typically piecewise linear) of the coefficient that is being varied, even if there are integrality constraints, e.g., as in the TSP. See Geoffrion & Nauss, Man. Sci. 1977. For arbitrary coefficients in the model, not just the objective, things are a little messier, e.g., see Schrage & Wolsey, Operations Research, 1985.