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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.