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?


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.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.