Degeneracy

From Glossary

Jump to: navigation, search

The solution LaTeX: (x, y, s) to the primal-dual pair of linear programs:

LaTeX: \min \{c^Tx : x \ge 0, \; Ax = b\} and LaTeX: \max \{y^Tb: s \ge 0, \; yA + s = c\}

is degenerate if it is not strictly complementary ---i.e. LaTeX: x_i = s_i = 0 for some LaTeX: i. The pair LaTeX: (x_i, s_i) is primal degenerate if there is an optimal solution LaTeX: x' such that LaTeX: x'_i > 0. Similarly, the pair is dual degenerate if there is a dual optimal solution LaTeX: (y', s') such that LaTeX: s'_i > 0.

With regards to a basic optimal solution, such a solution is (primal) degenerate when some basic variable is at one of its bound values (canonically zero). A basic optimal is dual degenerate if one of its nonbasic variables has a zero reduced cost. Geometrically, this corresponds to a degenerate polyhedron. Suppose we have LaTeX: \{x: Ax \le b\} (where LaTeX: A is LaTeX: m by LaTeX: n). This polyhedron is degenerate if there exists an extreme point that is an element of the intersection of more than LaTeX: n hyperplanes. The pyramid is degenerate because four planes meet at a point. (Example.)

Algorithmically, degeneracy can cause cycling in the simplex method.

Views
Personal tools