I am currently dealing with a problem of the following form \begin{alignat}{2} &\underset{x, y \in \mathbb{R}^n}{{\text{min}}} && e^T x \nonumber\\ &\text{sub to} \hspace{0.05in}&& \nonumber\\ & \hspace{0.05in}&& x = y \nonumber\\ & \hspace{0.05in}&& Ax \leq b \nonumber \\ & \hspace{0.05in}&& Cy \leq d \nonumber\\ & \hspace{0.05in}&& x, y \in \lbrace{0,1\rbrace}^n \nonumber \end{alignat} where A, C are totally unimodular matrices. I was wondering if there has been any theoretical work on problems with this type of constraints (intersection of TUMs). I am okay with not solving it exactly, a good lower bounding procedure for the problem is also welcome. Currently, I can only think of a Lagrangian based approach. Are there other alternatives?
In case you are curious, the context from which this problem came to me is in the computation of the longest path on a DAG, encoded using matrix $A$. However, the edges occurring on the longest path need to satisfy certain constraints, which are represented in $C$.
