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.