將DNF公式表示爲ILP約束

Question

有沒有將DNF公式轉換爲ILP約束的方法？ 例如，假設我已經在按照以下公式：

(x_1 and x_2 and x_3) or (not x_1 and x_2 and not x_3) 

如何寫爲ILP？

我知道它可以轉換成equisatisfiable CNF表達式，然後轉換成ILP，但這可以是子句/變量的指數大小。

Answer 1

喜歡的東西：

y1<=x1 
y1<=x2 
y1<=x3 
y1>=x1+x2+x3-2 
y2<=1-x1 
y2<=x2 
y2<=1-x3 
y2>=1-x1+x2+1-x3-2 
y>=y1 
y>=y2 
y<=y1+y2 
all variables in {0,1} 

結果將在Ÿ