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$.

  • 1
    $\begingroup$ Just an interesting observation, exact matching problem is such an intersection. Also, I think it is cleaner to remove $y$ completely by replacing $y$ with $x$. $\endgroup$ – Chao Xu Oct 17 '18 at 17:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.