Stability region

From Glossary

Jump to: navigation, search

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.


Views
Personal tools