Stability Radius for the Shortest Path Problem

Initializing live version
Download to Desktop

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.

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.

[more]

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:

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].

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.

[less]

Contributed by: Olia Karelkina (February 2016)
Open content licensed under CC BY-NC-SA


Snapshots


Details

References

[1] N. Chakravarti and A. P. M. Wagelmans, "Calculation of Stability Radii for Combinatorial Optimization Problems," Operations Research Letters, 23(1–2), 1998 pp. 1–7. doi:10.1016/S0167-6377(98)00031-5.

[2] V. Emelichev and D. Podkopaev, "Quantitative Stability Analysis for Vector Problems of 0-1 Programming," Discrete Optimization, 7(1-2), 2010 pp. 48–63. doi:10.1016/j.disopt.2010.02.001.



Feedback (field required)
Email (field required) Name
Occupation Organization
Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback.
Send