 # Stability region

The set of parameter values for which an optimal solution remains optimal. This arises naturally when solving combinatorial programs, where a solution is often a subgraph, such as a tree, and the question is for what range of arc weights is this subgraph optimal (such as a spanning tree that is minimum for given weights). More generally, $LaTeX: x$ could be a solution generated by some algorithm, $LaTeX: A$, from an initial value $LaTeX: x_0.$ Then, suppose the feasibility region depends on the parameter $LaTeX: p$, say $LaTeX: F(p),$ and the objective also depends on $LaTeX: p$, say $LaTeX: f(x;p).$ Let $LaTeX: X(p,A,x_0)$ denote the generated solution from algorithm A, starting at $LaTeX: x_0,$ with parameter value $LaTeX: p.$ Let the parameter set be $LaTeX: P$ (which includes $LaTeX: p^*$). The stability region of $LaTeX: x^* = X(p^*,A,x_0)$ is $LaTeX: \textstyle \{ p \in P: x^* =& X(p,A,x_0)\}.$ The algorithm may be a heuristic, so $LaTeX: x^*$ need not be optimal. For example, one could use an n-Opt heuristic for the travelling salesman problem, so x represents a tour. The parameters could be the costs, or they could be the location of each point in a Euclidean TSP. The stability region is the set of costs, or coordinates in the plane, for which the tour generated by n-Opt is the same.