# Degeneracy

### From Glossary

The solution to the primal-dual pair of linear programs:

is *degenerate* if it is not strictly complementary
---i.e. for some . The pair is *primal degenerate* if there is an optimal solution such that . Similarly, the pair is *dual degenerate* if there is a dual optimal solution such
that .

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 (where is by ). This polyhedron is degenerate if there exists an extreme point that is an element of the intersection of more than hyperplanes. The pyramid is degenerate because four planes meet at a point.
(Example.)

Algorithmically, degeneracy can cause cycling in the simplex method.