0
$\begingroup$

I have a primal problem that is a network-flow:

$$ min_x \sum_{a \in A} c_a x_a \\ \text{s.t.} \sum_{a \in A:n = v} X_{a}-\sum_{a \in A:n' = v} X_{a} = \begin{cases} \;\;\;1, \; v=n^{in} \\ -1, \; v=n^{out} \\ \;\;\;0, \; v \in V \setminus \{n_u^{in},n_u^{en}\} \end{cases} \\ X_{0}+ \sum_{a\in A \setminus \{0\}} X_{a} = 1 \\ X_{a} \leq X_{e} \;\;\;\;\;\;\forall a\in A^{special}, e \in A^{special}_a \\ X_{a}\in \{0,1\} \;\;\;\;\forall a\in A \\ $$

The first constraint is the continuity conservation, the second is that if it takes arc $0$ it cannot take nothing else and constraint 3 means that if it takes an special arc $a$, then all the arcs in $A_a$ have to activate. And constraint 4 is the binary nature of the variable (which I can relax to be $\in [0,1]$).

The dual of this problem is (or I think it is): $$ \max_{\pi} \pi_{n^{in}}^1 - \pi_{n^{out}}^1 + \pi^2 \\ \textbf{s.t.} \;\; \pi_{n^{in}}^1 - \pi_{n^{out}}^1 + \pi^2 + \pi^4_{0} \leq c_0 \\ \pi_{n^{in}}^1 - \pi_{n^{out}}^1 + \pi^2 + \pi^4_{0} \leq c_0 \\ \pi_{n^{in}}^1 - \pi_{n^{out}}^1 + \pi^2 - \sum_{e \in A^a} \pi^3_e + \pi^4_{a} \leq c_a \;\; \forall a \in A^{special} \\ \pi_{n^{in}}^1 - \pi_{n^{out}}^1 + \pi^2 + \sum_{e \in A^{special}} \pi^3_e + \pi^4_{a} \leq c_a \;\; \forall a \in A^{a} \\ \pi_{n^{in}}^1 - \pi_{n^{out}}^1 + \pi^2 + \sum_{e \in A^{special}} \pi^3_e + \pi^4_{a} \leq c_a \;\; \forall a \in A \setminus A^{a} \setminus A^{special} \setminus \{0\} $$

How do I interpret the dual constraints?

$\endgroup$

0

Your Answer

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