2
$\begingroup$

We consider a polyhedron $P = \{ x \in \Bbb R^n \mid Ax \leq b\} \neq \emptyset$, $A \in \Bbb R^{m \times n}$, $b \in \Bbb R^m$, $A$ with full column rank. With those hypotheses, we know that $P$ has vertices.

Each vertex $v \in P$ can be described by a set of rows of $A$ indexed by $B \subseteq \{1, ..., m\}$, called a basic feasible basis, such that $\lvert B \rvert = n$, the submatrix $A_B$ (the rows from $A$ indexed by $B$) has full rank, and $A_Bv = b_B$.

We have degeneracy when a vertex can be described by two different basis. If this happens, does it mean that $P$ has at least one redundant inequality (i.e. one that can be deduced from the others) ? If not, what hypotheses should we add to avoid degeneracy ?

$\endgroup$
0
$\begingroup$

The answer is yes: degeneracy implies at least one redundant constraint. See the link in this answer for an example.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.