3
$\begingroup$

I'm currently studying about totally unimodular.

I was reading this link: https://ostad.nit.ac.ir/upload/Integer_Programming_1.pdf, from page 38-41 and I came across the statement:

'It is clear that when matrix A is totally unimodular, the linear programming relaxation solves the IP: $\max\{cx:Ax \leq b, x \in Z_{+}^n\}.$'

I've read and understand about TU (totally unimodular) based on the link above and about LP relaxation.

Question: However, I still do not know how do I prove the statement above?

What I know: I know that if $A$ is TU then $(A, I)$ is TU for an identity matrix $I$. Also, as stated in the book that

'From linear programming theory, we know that basic feasible solutions take the form:. $x = (x_B,x_N) = (B^{-1} b, 0)$ where $B$ is an $m \times m$ nonsingular submatrix of $(A, I)$ and $I$ is an $m \times m$ identity matrix.

Observation 3.1 (Sufficient Condition) If the optimal basis $B$ has $\det(B) = ±1$, then the linear programming relaxation solves IP.'

My Hypothesis: Does a TU matrix $A$ always have a basis B such that $\det(B) = \pm 1$? But if $A$ is TU, all its square submatrix is either 0,-1, or 1 and not 1 or -1.

Extra Note: I am working on some shortest path inner problem of a variable $X_{ij}$ (the original model is bi-level) where $(i,j)$ represents the arc in the graph. The paper stated that since the inner problem (of the bi-level) is unimodular, we can use LP relaxation in order to use KKT to turn the bi-level into single level.

What I don't know: I do not know anything about polyhedron.

$\endgroup$
2
  • $\begingroup$ "$X_{ij}$ is unimodular" (meaning the matrix of $X$ values is unimodular) seems unlikely. Is the paper actually saying the coefficient matrix is unimodular (and, if so, is the paper saying the matrix is totally unimodular or just unimodular)? $\endgroup$
    – prubin
    Commented Sep 20, 2022 at 19:24
  • $\begingroup$ You are right. I made a mistake there. What I meant is 'the inner problem is unimodular.' $\endgroup$ Commented Sep 20, 2022 at 19:38

1 Answer 1

2
$\begingroup$

Does a TUM matrix $A$ always have a square submatrix $B$ with determinant $\pm 1?$ Technically, no. A matrix entirely filled with zeroes is TUM but obviously has no nonsingular submatrices. In the context of a linear program, the logic is as follows. Assume the problem is in canonical form (all constraints other than sign restrictions are equalities, say $Ax=b$). If $A$ is $m\times n$ and has full row rank, it will have at least one nonsingular $m\times m$ submatrix. If $A$ does not have full row rank, either the constraints $Ax=b$ are inconsistent (meaning the problem is infeasible) or you can eliminate redundant constraints until you are left with a smaller constraint matrix that does have full row rank.

Now assume that $A$ has full row rank. Since $A$ is TUM, any basis matrix $B$ is TUM, which means that $B^{-1}$ is integer-valued. It then follows that $B^{-1}b$ is integer-valued provided that $b$ is integer valued.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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