# When does total unimodularity implies integrality of solutions?

In Gartner & Matousek's book on linear programming, they prove the following lemma (Lemma 8.2.4, page 145):

Let us consider a linear program with $$n$$ nonnegative variables and $$m$$ inequalities of the form:

maximize $$c^T x$$

subject to $$A x \leq b$$ ,$$x\geq 0$$

where $$b\in \mathbb{Z}^m$$. If $$A$$ is totally unimodular, and if the linear program has an optimal solution, then it also has an integral optimal solution $$x^*\in \mathbb{Z}^n$$.

My question is: is the same theorem also true when the constraints have different signs, e.g., some constraints have "$$\leq$$" and some have "$$\geq$$" and some have "$$=$$"?

I know that every LP with such constraints can be converted to standard form, but, does the conversion preserve the total-unimodularity of the constraint matrix?

• After converting to standard form, the new coefficient matrix will also be totally unimodular. – Yuval Filmus Jan 28 at 3:47