Archive for September, 2009

The following generic 0-1 programming form can be solved by finding a minimum-cut of a bipartite directed graph. Max{Sigma{A(i)*X(i)}+Sigma{B(i)*Y(i)}-Sigma{C(i,j)*X(i)*Y(j)}} (C(i,j)>0).
To construct the network, first construct vertices one source S, one destination T, the left vertex set {X(1),X(2),…} and the right vertex set {Y(1),Y(2),…}, and add directed edges as the following rules:

  • For each A(i)>0, add S–>X(i) with capacity A(i).  (X(i)=1 <===> S–>X(i) not in the cut)
  • For each A(i)<0, add X(i)–>T with capacity -A(i).
  • For each B(i)>0, add Y(i)–>T with capacity B(i). (Y(i)=1 <===> Y(i)–>T not in the cut)
  • For each B(i)<0, add S–>Y(i) with capacity -B(i).
  • For each C(i,j)>0, add X(i)–>Y(j) with capacity C(i,j).

Read Full Post »