# Stability region

### From Glossary

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, could be a solution generated by some algorithm, , from an initial value Then, suppose the feasibility region depends on the parameter , say and the objective also depends on , say Let denote the generated solution from algorithm A, starting at with parameter value Let the parameter set be (which includes ). The stability region of is
The algorithm may be a heuristic, so 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.