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?



Fractional values in linear programming
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.


