4
$\begingroup$

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?

$\endgroup$

0

Your Answer

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