When solving instances of the following linear program (LP), I always get an integral (actually binary) solution. Is it just a coincidence or is it possible to prove that there always exists a binary solution? (Sorry if the definitions are hard to follow, I also included an example at the end.)
The LP is $$ \begin{align*} &\text{maximize }& &j^\prime x\\ &\text{subject to }& &Ax \leq b\\ & && 0\leq x_i \leq 1 \quad \forall i \end{align*} $$
** update: the last constraint ($0\leq x_i \leq 1$) is redundant and not needed.
Where $j$ is a vector of ones, $A$ has the following form $$ A = \begin{bmatrix} I & I & Z\\ I & Z & Z\\ Z & I & Z\\ Z & Z & I\\ -Y & -Y & I\\ Y & -Y & -I \end{bmatrix} $$ $I$ is the $n \times n$ identity, $Z$ is $n \times n$ zeros, and $Y \in \{0, 1\}^{n\times n}$ such that each column sums up to one (exactly one 1 in each column) and the index of the 1 in each column is greater or equal to the index of the one in previous column (see the example at the bottom). Moreover any of the last $n$ rows of $A$ may be multiplied by -1.
$$ b= \begin{bmatrix} i\\ r_1\\ r_2\\ i\\ z\\ z \end{bmatrix}$$
Where $i$ is a vector of ones of length $n$, $z$ is a vector of zeros of length $n$, $r_1 \in \{0,1\}^n$, $r_2\in \{0,1\}^n$ (random zero-one vectors of length n)
I found literature describing that if $A$ is unimodular, that is a sufficient condition for the solution being integral. Unfortunately, in general, A is not totally unimodular.
A weaker sufficient condition would be total dual integrality (TDI), saying that if for all integral vectors $j$, the dual program has an integral solution whenever the optimal value is finite. And the every vertex of the solution set of a TDI system is integer-valued. But IMHO this would include proving that the dual is integral, which would just raise similar questions. Moreover, I'm not even sure that the TDI condition holds.
Another way of doing this could be using the structure of $j$ (all ones), and show only for this direction that the optimal solution is indeed an integral-value vertex. So the question is if there is anything particular in the structure of this problem ($A$, $b$, $j$) that can be a condition for integral solution.
Example with $n=3$: $$ Y = \begin{bmatrix} 0&0&0\\ 1&1&0\\ 0&0&1 \end{bmatrix}$$ $$ A = \begin{bmatrix} 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\ -1 & -1 & 0 & -1 & -1 & 0 & 0 & 1 & 0\\ 0 & 0 & -1 & 0 & 0 & -1 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\ 1 & 1 & 0 & -1 & -1 & 0 & 0 & -1 & 0\\ 0 & 0 & 1 & 0 & 0 & -1 & 0 & 0 & -1 \end{bmatrix},\;\; b= \begin{bmatrix} 1\\ 1\\ 1\\ 1\\ 1\\ 1\\ 1\\ 1\\ 1\\ 1\\ 1\\ 1\\ 0\\ 0\\ 0\\ 0\\ 0\\ 0\\ \end{bmatrix} $$
The solution for this instance is 5, all the variables are found binary (by gurobi), however there exist non binary solutions as well with the same optimal value.