Given a directed graph $G=(V,E)$, I have the following integer program-

\begin{align} \max & \sum_{(u,v) \in E} \sum_{s \in S} w_{uv} z_{uv,s} + \sum_{v \in V} \sum_{s \in S} b_{v,s} x_{v,s} \\ \text{subject to} \quad & \sum_{s \in S} x_{v,s} = 1, \quad \forall v \in V \\ & z_{uv,s} \leq x_{u,s}, \quad \forall (u,v) \in E, \forall s \in S \\ & z_{uv,s} \leq x_{v,s}, \quad \forall (u,v) \in E, \forall s \in S \\ & z_{uv,s} \geq x_{u,s} + x_{v,s} - 1, \quad \forall (u,v) \in E, \forall s \in S \\ & x_{v,s} \in \{0, 1\}, \quad \forall v \in V, \forall s \in S \\ & z_{uv,s} \in \{0, 1\}, \quad \forall (u,v) \in E, \forall s \in S \end{align}

The basic idea of this program is that at each node in this directed graph I can install a certain technology $s\in S$. In the program, $w_{uv} $ is the weight of the arc $(u,v)\in E$, given by a positive real number. Further, $b_{v,s}$ is some benefit associated with the technology $s \in S$, which is again a positive real number. I have run the relaxation of this integer program for a couple of instances, and I am always obtaining an integral solution. Therefore, I would like to prove/disprove that the constraint matrix of the above integer program is/is not totally unimodular.

I know that total unimodularity has a couple of equivalent conditions, but none of them seem to in this case (or maybe, I am missing some crucial detail).

Could anyone point out any ideas in this direction?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.