What is an unimodular problem?

121 Views Asked by At

Given an optimization problem below: $$ \min_{Y^m_{ij} \in \{0,1\}} \sum_{p \in P} \sum_{(i,j)\in A} \sum_{c \in C} n^c \rho_{ij}^{p,m(c)} X_{ij}^c\\ \text{where } X_{ij}^c \text{ solves:}\\ \min \sum_{c \in C} \sum_{(i,j) \in A} n^c l_{ij} X_{ij}^c\\ \text{s.t. }\\ \sum_{(i,k) \in A} X_{ik}^c - \sum_{(k,i) \in A} X_{ki}^c = \begin{cases} +1, &\text{if } i = o(c)\\ -1, &\text{if } i = d(c), \forall i \in N, c \in C\\ 0, &\text{o.w} \end{cases}\\ X_{ij}^c \leq Y_{ij}^{m(c)} \;\; \forall (i,j) \in A, c \in C\\ X_{ij}^c \in \{0,1\} \;\; \forall (i,j) \in A, c \in C $$

with $n^c, \rho_{ij}^{p,m(c)},$ and $ l_{ij}$ as parameters.

It is stated that "Once the $Y_{ij}^m$ values are given, the inner problem is unimodular. Hence, the integrality requirements ($X_{ij}^c \in \{0,1\}$) can be replaced by $X_{ij}^c \geq 0$ without the loss of optimality.

Question: What does unimodular mean in this problem? How does it affect the integrality requirements $X_{ij}^c$?

What I know: I found a definition that states; "A matrix A is totally unimodular if every square submatrix of A has determinant +1,-1, or 0." But I'm not sure how to use that definition in the problem above.

Thank you for the help.