Exercise 2.11

Question

Let $P = \left\{\mathbf{x} \in \mathfrak{R}^n \mid \mathbf{A}\mathbf{x} \geq \mathbf{b} \right\}$. Suppose that at a particular basic feasible solution, there are $k$ active constraints, with $k>n$. Is it true that there exist exactly ${k \choose n}$ bases that lead to this basic feasible solution?

Elu Thingol · Accepted Answer

No. There is a maximum of ${n \choose k}$ bases because there are that many ways to choose $n$ out of $k$ possible bases, but not all combinations have to have linearly independent, so there may be less than ${n \choose k}$ bases. As a counterexample, consider the following polyhedron
$$\left\{ \mathbf{x}\in\mathfrak{R}^2\ \left|\ 
\begin{bmatrix}
1 & 0\
0 & 1\
2 & 0
\end{bmatrix} \begin{bmatrix} x_1 \ x_2 \end{bmatrix} \geq \begin{bmatrix} 0\ 0\ 0 \end{bmatrix}ight.ight\}.$$
At the point $\mathbf{0}$ we have $2$ linearly independent constraints $[1,0]$ and $[0,1]$; all equality constraints are active and the point is feasible. Therefore, $\mathbf{0}$ is a basic feasible solution. A simple case-by-case inspection, however, reveals that there are only two combinations of linearly independent columns: $\{[1,0], [0,1]\}$ and $\{[0,1],[2,0]\}$. This is less that ${ 3 \choose 2 } = 3$.

Exercise 2.11

Answers

Comments

Exercise 2.11

Answers

Comments

Add answer