Fractional values in linear programming

Question

Consider the linear programming problem \begin{align} f^* = \max_{x}&~p^Tx~\\~&A^Tx\leq b~,~0\leq x_i\leq 1 \end{align}where $p$ is a $n\times 1 $ vector, $A$ is a $n\times c$ matrix and $b$ is a $c \times 1$vector. Here $x=[x_1,\dots,x_n]$ is the $n \times 1$ vector to be found. Thus, in addition to the box constraint $0\leq x_i\leq 1$, we have $c$ constraints. It is also known that $p,A,b$ are all element-wise positive.

I randomly generated $p,A,b$ such that each entry is i.i.d and is uniformly distributed in the interval $[0,1]$. Note that this meets the problem set-up. I observed that whenever the problem was feasible, the optimal solution $x^*=[x_1^*,\dots,x_n^*]$ had a interesting property. The number of fractional $x_i^*$ (i.e. $0<x_i^*<1$) were atmost $c$. Every other $x_i^*$ belonged to $\{0,1\}$ (accounting for rounding). Is there anything going on here?

Answer 1

Yes, this is a known consequence of the fact that there always exists an optimal solution that is basic (an extreme point of the feasible region). This property is the foundation of the simplex method, which moves from one basis to another in each iteration.