Algorithm4のRefactoring

以前頓挫した、ペア制約のLP化を再考してみました。

A:f1(x0,x1,x2...)≤b1;

B:f2(x0,x1,x2...)≤b2;

Implication A→Bは、

!A+B

そのソフト化は、Binary Variable Cを追加して

!A+B+C >=1;-----(1)

Minimize:  ...+C*Cweight;

とします。ここで、Cは、0になるように作用することに注意します。すると(1)式より

！Aもしくは、Bが１になるように作用することが分かります。なので、

！A:  f1(x0,x1,x2...)+M(1-A) ≧b1+1;

   B:  f2(x0,x1,x2...) -M(1-B) ≤b2;

とすれば、A＝＝１、B==1側に自然に作用します。（Mは、BigMです。）

上のように定式化すれば、ペア制約ImplicationもLP化(Linear　Programming)出来そうです。