So I have a graph $G=(V,E)$ with max capacity and minimal flow on the edges (denoted $C_{i,j}, l_{i,j}$ respectively).

In addition to that I have a leaking component $r_v$ for all $v\in V\backslash \{s,t\}$ so that if flow $F$ goes into vertex $v$, only $F(1-r_v)$ comes out of it.

Formulate the linear program for the max flow problem and the dual problem.

So the max flow program is as follows:

$$max \sum_{(j,t)\in E}f_{j,t}$$


$$(1-r_i)\sum_{(k,i)\in E}f_{k,i}-\sum_{(i,j)\in E}f_{i,j}=0\ \ \ \ \ \ \ \ \ \ \ \ \forall v\in V\backslash \{s,t\}$$

$$f_{i,j}\leq c_{i,j} \ \ \ \ \ \ \ \ \ \forall(i,j)\in E $$

$$f_{i,j}\geq l_{i,j}\ \ \ \ \ \ \ \ \ \forall(i,j)\in E $$

I have trouble getting the dual problem down, I know it's the min cut, but all the additional constraints have me confused. Can anyone help?

  • $\begingroup$ can you make an attempt? $\endgroup$ – LinAlg Jan 10 '17 at 16:58
  • $\begingroup$ You have a $k$ in your second equation, but $k$ is not in the question. Possible typo? $\endgroup$ – unseen_rider Mar 5 '17 at 9:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.