Dual Of Integer Network Formulation

Question

I have the following IP and I wonder how to write the dual of it as a network flow problem:

\begin{align} \max & \sum_{i \in N} w_ix_i \\[4pt] \text{s.t. } & x_i \leq x_j, \forall (i,j) \in A \\[10pt] & 0 \leq x_i \leq 1, \forall i \in N \end{align}

I was thinking that the dual could be:

\begin{align} \min & \sum_{i \in N} z_{i} \\[4pt] \text{s.t. } & \sum_{(i,j)} y_{ij} - \sum_{(j,i)} y_{ji} \geq 0, \forall i \in N \\[10pt] &z_{i} \geq w_{i} , \forall i \in N\\ & y_{ij} \geq0 , \forall (i,j) \in A \end{align}

but I am not sure. what changes do I need to do to make the dual formulation correct?

Answer 1

There are three errors: (1) Because $y_{ij}$ is associated to the constraint where the right hand side is 0 ($x_i - x_i \leq 0$), it should not appear in the objective. (2) The coefficients $w_i$ seem to be missing in the dual. (3) You currently do not have a dual variable associated to the constraint $x_i \leq 1$.

This seems to be the correct dual to me: \begin{align} \min & \sum_{i \in N} z_{i} \\[4pt] \text{s.t. } & z_i + \sum_{j : (i,j) \in A} y_{ij} - \sum_{j : (j,i)\in A} y_{ji} \geq 0, \forall i \in N \\[10pt] & y_{ij} \geq0 , \forall (i,j) \in A \\ & z_i \geq 0, \forall i \in N \end{align}