Editing Integer programming (section)

===Using total unimodularity===

While in general the solution to LP relaxation will not be guaranteed to be integral, if the ILP has the form <math>\max\mathbf{c}^\mathrm{T} \mathbf{x}</math> such that <math>A\mathbf{x} = \mathbf{b}</math> where <math>A</math> and <math>\mathbf{b}</math> have all integer entries and <math>A</math> is [[unimodular matrix#Total unimodularity|totally unimodular]], then every [[basic feasible solution]] is integral.  Consequently, the solution returned by the [[simplex algorithm]] is guaranteed to be integral.  To show that every basic feasible solution is integral, let <math>\mathbf{x}</math> be an arbitrary basic feasible solution . Since <math>\mathbf{x}</math> is feasible,
we know that <math>A\mathbf{x}=\mathbf{b}</math>. Let <math>\mathbf{x}_0=[x_{n_1},x_{n_2},\cdots,x_{n_j}]</math> be the elements corresponding to the basis columns for the basic solution <math>\mathbf{x}</math>. By definition of a basis, there is some square submatrix <math>B</math> of
<math>A</math> with linearly independent columns such that <math>B\mathbf{x}_0=\mathbf{b}</math>.

Since the columns of <math>B</math> are linearly independent and <math>B</math> is square, <math>B</math> is nonsingular,
and therefore by assumption, <math>B</math> is [[unimodular matrix|unimodular]] and so <math>\det(B)=\pm1</math>. Also, since <math>B</math> is nonsingular, it is invertible and therefore <math>\mathbf{x}_0=B^{-1}\mathbf{b}</math>. By definition, <math>B^{-1}=\frac{B^\mathrm{adj}}{\det(B)}=\pm B^\mathrm{adj}</math>. Here <math>B^\mathrm{adj}</math> denotes the [[Adjugate matrix|adjugate]] of <math>B</math> and is integral because <math>B</math> is integral.  Therefore,
<math display=block>
\begin{align}
&\Rightarrow B^{-1}=\pm B^\mathrm{adj} \text{ is integral.} \\
&\Rightarrow \mathbf{x}_0=B^{-1}b \text{ is integral.} \\
&\Rightarrow \text{Every basic feasible solution is integral.}
\end{align}
</math>
Thus, if the matrix <math>A</math> of an ILP is totally unimodular, rather than use an ILP algorithm, the simplex method can be used to solve the LP relaxation and the solution will be integer.