Find the edges emanating from a given vertex in a polyhedron defined by $P=\{ x\in \mathbb{R}^n \mid Ax=b, x\geq0 \}$

199 Views Asked by At

Suppose my polyhedron $P$ is defined as $P=\{ x\in \mathbb{R}^n \mid Ax=b, x\geq0 \}$. I have $x_0$, which is a vertex of $P$. How to find the edges emanating from $x_0$?

In other words, I want to find the set $D={ d_1, \cdots, d_n}$ such that $x_0+\lambda d_i$ is a vertex for some $\lambda>0$.

Is there a way of getting $D$ using $A$, $b$ and $x_0$? This is needed to code up a cutting plane algorithm for bilinear programming.

Thanks a lot!