# How to interpret this integer program

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.

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

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.
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$$