I'm currently studying about totally unimodular.
I was reading this link: https://ostad.nit.ac.ir/upload/Integer_Programming_1.pdf, from page 38-41 and I came across the statement:
'It is clear that when matrix A is totally unimodular, the linear programming relaxation solves the IP: $max\{cx:Ax \leq b, x \in Z_{+}^n\}.$'
I've read and understand about TU (totally unimodular) based on the link above and about LP relaxation.
Question: However, I still do not know how do I prove the statement above?
What I know: I know that if $A$ is TU then $(A, I)$ is TU for an identity matrix $I$. Also, as stated in the book that
'From linear programming theory, we know that basic feasible solutions take the form:. $x = (x_B,x_N) = (B^{-1} b, 0)$ where $B$ is an $m \times m$ nonsingular submatrix of $(A, I)$ and $I$ is an $m \times m$ identity matrix.
Observation 3.1 (Sufficient Condition) If the optimal basis $B$ has $det(B) = ±1$, then the linear programming relaxation solves IP.'
My Hypothesis: Does a TU matrix $A$ always have a basis B such that $det(B) = \pm 1$? But if $A$ is TU, all its square submatrix is either 0,-1, or 1 and not 1 or -1.
Extra Note: I am working on some shortest path inner problem of a variable $X_{ij}$ (the original model is bi-level) where $(i,j)$ represents the arc in the graph. The paper stated that since $X_{ij}$ is unimodular, we can use LP relaxation in order to use KKT to turn the bi-level into single level.
What I don't know: I do not know anything about polyhedron.
Thanks in advance.