Show that the following matrix or its corresponding system of constraints is Totally Unimodular (TU)

41 Views Asked by At

I have the following Integer Linear Program constraints: \begin{align} \sum_{c\in C}\sum_{i = 1}^{K^c} x_i^c(t) \leq \Lambda, \forall \: t \\ \sum_{t=0}^{H}\sum_{i = 1}^{K^c} x_i^c(t)\leq \Lambda^c, \: \forall \: c\\ \end{align} \begin{align} \sum_{j = i}^{H+i} x^c_j(H-j+i) &\leq Q_{H+i}^c(0), \; H+i<K^c \\ \sum_{j = i}^{K^c} x^c_j(H-j+i) &\leq Q_{K^c}^c(H-K^c+i), \; H+i\geq K^c \; \& \; H<K^c \end{align} \begin{align} \sum_{j = i}^{K^c} x^c_j(H-j+i) &\leq Q_{K^c}^c(H-K^c+i), H \geq K^c \end{align} All bounds $\Lambda,\Lambda^c,Q_i^c(t) \; \forall \;c\in C,1\leq i \leq K^c,0\leq t \leq H$ are non-negative integers. I am maximizing $\sum_{c,i,t}x_i^c(t)$ where $x_i^c(t)\in \mathcal{N\cup{0}}$. The LP version of the problem yields integer solutions as well which makes me wonder if the constraint matrix is TU but I am unable to construct a proof. As a start, I considered $c=1$ $K^1 = 3$, $H = 1$ which gives me the following constraint matrix (since $c=1$ I have omitted the superscript): \begin{equation} \begin{pmatrix} x_1(0) & x_2(0) & x_3(0) & x_1(1) & x_2(1) & x_3(1) \\ 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ \end{pmatrix} \end{equation} I have checked that this is TU. Any help would be much appreciated.