Stability Radius for the Shortest Path Problem
Stability Radius for the Shortest Path Problem
In stability theory, a quantitative characteristic called the stability radius is defined as the limit level of perturbations of problem parameters preserving optimality of a single solution (or of the solution set). These perturbations are caused by the various factors of uncertainty and randomness, such as inadequacy of mathematical models to real processes, rounding errors, calculation errors, and so on.
This Demonstration addresses the approach proposed in [1] to compute the stability radius of an optimal solution to the shortest path problem. The stability radius is the largest non-negative that satisfies the inequality:
ρ
min
x∈X
n
∑
i=1
x
i
c
i
d
i
n
∑
i=1
c
i
x
i
n
∑
i=1
x
i
The right-hand side is a linear function in the variable . The left-hand side is the value function of a parametric version of the initial shortest path problem, where the objective coefficients are linear functions of . Call this the value function . It is well-known that is a continuous, piecewise-linear, and concave function of . The detailed steps to construct function can be found in [1].
ρ
ρ
v(ρ)
v(ρ)
ρ
v(ρ)
The algorithm is tested for two graph types. The "LayerGraph" is generated by several so-called vertex layers. The vertices on the same layer are not connected and each vertex on any layer is adjacent to all vertices from adjacent layer(s). In the "NormalGraph", the edges are generated with equal probability for all pairs of vertices. Both graphs are connected and have at least one path between given source and destination. Note that edge weights correspond to edge colors.