1

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.

TYZ
  • 377

2 Answers2

0

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.

Math1000
  • 36,983
0

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

RobPratt
  • 45,619