1
$\begingroup$

I'm having problem understanding the min weight st-cut integer programming in this wiki page: https://en.wikipedia.org/wiki/Max-flow_min-cut_theorem

In the min-cut dual part, it has

$$d_{ij}-p_i+p_i \geq 0 \;\; \forall (i,j) \in E$$ where $d_{ij}$ is binary: 1 if the edge is selected in st-cut 0 otherwise. p_i is 1 if vertex i is in the same side as s and 0 if in the same side as p. (you can read the original wiki for more information).

I'm not able to understand how this constraint will make this IP work.

$\endgroup$
2
  • $\begingroup$ look at every cases $p_i - p_j = 0$ or $1$ or $-1$ $\endgroup$
    – reuns
    Jan 21 '16 at 10:49
  • $\begingroup$ @user1952009 I did, but I don't understand why having this constraint to find the min weight st-cut $\endgroup$
    – TYZ
    Jan 21 '16 at 17:25
0
$\begingroup$

The source states $$d_{uv} - z_u+z_v\geqslant 0,\quad \forall (u,v)\in E, u\ne s, v\ne t$$ and is described is [a constraint per edge]. Since in the primal we had a varible for each edge, in the dual with have a constraint for each edge, whose constraint matrix coefficient is that of the transpose of the primal constraint matrix corresponding to that edge.

$\endgroup$
0
$\begingroup$

You have a typo. The second $p_i$ should instead be $p_j$. You want to enforce $$(p_i = 1 \land p_j = 0) \implies d_{i,j}=1.$$ Rewriting in conjunctive normal form somewhat automatically derives the desired linear constraint: $$ (p_i \land \neg p_j) \implies d_{i,j}\\ \neg (p_i \land \neg p_j) \lor d_{i,j}\\ \neg p_i \lor p_j \lor d_{i,j}\\ (1 - p_i) + p_j + d_{i,j} \ge 1\\ d_{i,j} \ge p_i - p_j $$

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.