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?

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.