We know that given a binary (0-1) linear program, we can find lower/upper bounds using its relaxation. But, there are instances (such as shortest path problem with non-negative cycles, bipartite matching, max-flow, etc) for which the feasible region of the relaxation actually has integral vertices. My question is about the methods we can use to prove this property for a given problem that we know for which this property holds. Is there a machinery for this or it is something creative and problem-based?
Update: Assume matrix $A$ is given as
[1 1 0 1 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0]
[1 1 1 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0]
[1 0 1 1 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0]
[0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0]
[0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0]
[0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0]
[0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0]
[0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0]
[0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1]
I tested this matrix by Matlab, and it is not TU. Given $d_n$, $n =1,\ldots,9$, the problem is
\begin{align} \min \quad &\sum_{n=1}^{22} b_n c_n \\ s.t. \quad& A \begin{bmatrix} b_1 \\ \vdots \\ b_{22} \end{bmatrix}_{22 \times1} = \begin{bmatrix} 1 \\ \vdots \\ 1 \end{bmatrix}_{9 \times1}\\ & b_n \in \{0,1\}, \quad n=1,\ldots,22. \end{align} and its relaxation is: \begin{align} \min \quad &\sum_{n=1}^{22} b_n c_n \\ s.t. \quad& A \begin{bmatrix} b_1 \\ \vdots \\ b_{22} \end{bmatrix}_{22 \times1} = \begin{bmatrix} 1 \\ \vdots \\ 1 \end{bmatrix}_{9 \times1}\\ & b_n \geq 0, \quad n=1,\ldots,22. \end{align} where \begin{align} c_n = \max\{A[1,n]*d_1,A[2,n]*d_2,\ldots, A[9,n]*d_9 \}. \end{align} For example, $c_1 = \max\{d_1,d_2,d_3\}$ and $c_3 = \max\{d_2,d_3\}$.
What can we do to show this: "The vertices of the polytope of the relaxation problem are integral"?
Then, instead of solving the IP, we can solve its LP relaxation.
Typically you show that the coefficient matrix is totally unimodular (TUM). Then by Cramer's rule any basic feasible solution is integral (if the right hand side is integral).
In the example in your initial question, the coefficient matrix is $\begin{pmatrix}1 & 1 \\ 1 & 1\end{pmatrix}$. The determinant of this matrix is $0$ while all submatrices have determinant $1$. So, this constraint matrix is TUM. Since the right hand side is integral, any basic feasible solution is integral too.
In the example in your updated question, it is merely luck that your solution is integral. If I solve it with a different objective function, I obtain a fractional solution: take $d_n=1$ for $n\in\{2,4,9\}$, $d_n=0$ otherwise. Then $c_n=1$ for $n \in\{1,2,3,7,8,11,13,15,17,22\}$, $c_n=0$ otherwise. When you use the variables $b_n$ for $n$ in $\{4,5,6,7,8,10,11,12,13\}$ as a basis in the simplex method, you obtain a fractional solution that is optimal. There are integral optimal solutions, but this fractional one proves that the relaxation is not equivalent to the original problem.