# Integral solution of LP with two-sided inequality constraint

I know the constraints matrix $A$ of a linear program $$\min c^Tx \text{ subject to } b\le Ax$$ is totally unimodular. So, the program has integral solutions for integral vector $b$.

Is this is also the case for the following problem: $$\min c^Tx \text{ subject to } b_1\le Ax\le b_2$$ where $b_1$ and $b_2$ are integral vectors and $A$ is totally unimodular. Does it have integral solutions, too?

## 1 Answer

The problem can be converted into standard form using slack variables $s_1$ and $s_2$. Then the two-sided problem is equivalent to $$\min c^Tx$$ subject to $$\pmatrix{ A & -I &0\\ A& 0&I}\pmatrix{x\\s_1\\s_2} = \pmatrix{b_1\\b_2}$$ and $$x\ge0, \ s_1\ge0, \ s_2 \ge0.$$ The matrix appearing above is totally unimodular:

• If $A$ is totally unimodular, then is $\pmatrix{-A\\A}$.
• If $B$ is totally unimodular, so is $\pmatrix{B & I}$.
• If $\pmatrix{C\\D}$ is totally unimodular, so is $\pmatrix{-C\\D}$.

These facts together prove that the system matrix above is totally unimodular as well.