2
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ Add noise to the distances, re-solve and compare the objective values $\endgroup$
    – fontanf
    Feb 3, 2022 at 6:55
  • 2
    $\begingroup$ 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. $\endgroup$ Feb 3, 2022 at 9:01

1 Answer 1

3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.