将 DNF 公式表示为 ILP 约束
Express DNF formula as ILP constraint
有没有办法将DNF公式转换为ILP约束？
例如，假设我有以下公式：
(x_1 and x_2 and x_3) or (not x_1 and x_2 and not x_3)
如何写成ILP？
我知道它可以转化为等可满足的CNF表达式，然后转化为ILP，但这可以是clauses/variables的指数大小。
类似于：
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}
结果将在 y 中可用
有没有办法将DNF公式转换为ILP约束？ 例如，假设我有以下公式：
(x_1 and x_2 and x_3) or (not x_1 and x_2 and not x_3)
如何写成ILP？
我知道它可以转化为等可满足的CNF表达式，然后转化为ILP，但这可以是clauses/variables的指数大小。
类似于：
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}
结果将在 y 中可用