Consider binary decision variables $x_{ij}$ and $y_j$ where $ i \in \{1,2,\ldots,I\}$ and $ j \in \{1,2,\ldots,J\}$ for fixed integers $I$ and $J$. Consider the following feasibility prolem: \begin{alignat}{3} \underset{\{x_{ij}\}, \{y_{j}\}}{\text{minimize}} & \hspace{2mm} && 0 \\ \text{subject to} & && \sum_{i=1}^{I} \sum_{j=1}^{J} x_{ij} c_{ij} \leq C \:, \\ & && \sum_{j=1}^{J} {x_{ij}} = 1 \quad \forall i \in [I] \:, \\ & && \sum_{j=1}^J y_{j} d_j \leq D \:, \\ & && y_j - \sum_{i=1}^I {x_{ij}} \leq 0 \quad \forall j \in [J] \:, \\ & && x_{ij}, y_j \in \{0,1\}\quad \forall i \in [I] , j \in [J] \:, \end{alignat} where all constants are positive and assume interegr if needed.
Can we say that the constraints are totally unimodular? If we remove the first constraint and relax the second equality constraint to $\leq 1$, then the resulting constraints are totally unimodular, by Theorem of sheet 10/29 of this lecture. However, adding constraint one violates ``no more than 2 nonzeros are in each column'' condition. Any suggestion?
If you look at sheet 4/29, you will see that one key property of TUM matrices is that all entries are restricted to $\lbrace -1,0,1 \rbrace$. So adding the first constraint will prevent the constraint matrix from being TUM unless all $c_{ij}$ are in $\lbrace -1,0,1 \rbrace$. Similarly, unless you can fix $y_j=0$ as Rob suggested (and remove $y$ entirely from the constraints), you would need $d_j \in \lbrace -1,0,1 \rbrace$ for all $j$.