It is well known, that the optimal tours are invariant under the addition of vertex weights; it is also known, that minimum spanning trees provide an upper bound on the length of the shortest Hamilton cycle in a graph and, that the MST is sensitive to the addition/subtraction of vertex weights, which makes it possible to penalize vertices with high degree in the MST and thus improve the upper bound in some cases.
Questions:
are TSP algorithms, that are based on polyhedral methods, such as e.g. Cut&Branch, sensitive to the addition/subtraction of vertex weights in the sense, that the execution path from the input of a TSP instance to reporting the optimal solutions can vary, if vertex weights are added/subtracted?
In case of an affirmative answer: what would be good criteria for the vertex weights to be added/subtracted (e.g. maximize sum of subtracted weights, that leave all edge weights non-negative; add large weights; add random weights)?
