Google或工具:如何计算复杂的或多层次的布尔约束
Google或工具:如何计算复杂的或多层次的布尔约束
提问于 2022-01-03 21:01:39
设置
我使用google或工具作为约束编程解决程序：
from ortools.sat.python import cp_model我定义了以下BoolVars
model = cp_model.CpModel()
a = model.NewBoolVar("a")
b = model.NewBoolVar("b")
c = model.NewBoolVar("c")
d = model.NewBoolVar("d")
e = model.NewBoolVar("e")
f = model.NewBoolVar("f")
g = model.NewBoolVar("g")问题
我需要在模型中添加一个复杂的布尔约束。有点像
(a || b) && (d || e) == g如何将这样的复杂布尔约束添加到模型中？
PS:我无法立即在网上找到这个信息，但是根据我得到的一个相关问题here和另一个人here的相关问题找到了一个解决方案。我在这里总结我的发现，在问答风格，希望他们将是有用的人。
回答 1
Stack Overflow用户
发布于 2022-01-03 21:01:39
这种约束不能立即添加到模型中。约束需要在其组件(和&或门)中拆分。每个基本组件都需要设置为一个新的BoolVar。然后将它们组合起来，以添加最后的约束。
分解为基本组件
我们将这样做如下：
(a || b) == c
(d || e) == f
(c && f) == g最后一个方程等价于原来的方程：
(a || b) && (d || e) == g在新的BoolVars中存储基本约束
可以用以下函数计算"OR“型方程：
def evaluate_or(a, b, c):
# Either a or b or both must be 1 if c is 1.
model.AddBoolOr([a, b]).OnlyEnforceIf(c)
# The above line is not sufficient, as no constraints are defined if c==0 (see reference documentation of
# "OnlyEnforceIf". We therefore add another line to cover the case when c==0:
# a and b must both be 0 if c is 0
model.AddBoolAnd([a.Not(), b.Not()]).OnlyEnforceIf([c.Not()])“和”类型的方程可以用以下函数进行类似的计算：
def evaluate_and(a, b, c):
# Both a and b must be 1 if c is 1
model.AddBoolAnd([a, b]).OnlyEnforceIf(c)
#What happens if c is 0? This is still undefined thus let us add another line:
# Either a or b or both must be 0 if c is 0.
model.AddBoolOr([a.Not(), b.Not()]).OnlyEnforceIf(c.Not())在这种特殊情况下，基本约束是OR门的两倍。我们把它们储存在c和f中：
evaluate_or(a, b, c)
evaluate_or(d, e, f)添加复杂约束
这现在非常简单，可以使用上一步的BoolVars和一个和门完成：
evaluate_and(c, f, g)讨论
任何复杂的约束都可以使用中间BoolVars和上面定义的OR和和门函数来添加。这个约束只需要分解成它的基本组件。
全程序
这是完整的节目：
from ortools.sat.python import cp_model
model = cp_model.CpModel()
a = model.NewBoolVar("a")
b = model.NewBoolVar("b")
c = model.NewBoolVar("c")
d = model.NewBoolVar("d")
e = model.NewBoolVar("e")
f = model.NewBoolVar("f")
g = model.NewBoolVar("g")
def evaluate_or(a, b, c):
# Either a or b or both must be 1 if c is 1.
model.AddBoolOr([a, b]).OnlyEnforceIf(c)
# The above line is not sufficient, as no constraints are defined if c==0 (see reference documentation of
# "OnlyEnforceIf". We therefore add another line to cover the case when c==0:
# a and b must both be 0 if c is 0
model.AddBoolAnd([a.Not(), b.Not()]).OnlyEnforceIf([c.Not()])
def evaluate_and(a, b, c):
# Both a and b must be 1 if c is 1
model.AddBoolAnd([a, b]).OnlyEnforceIf(c)
#What happens if c is 0? This is still undefined thus let us add another line:
# Either a or b or both must be 0 if c is 0.
model.AddBoolOr([a.Not(), b.Not()]).OnlyEnforceIf(c.Not())
#Add the constraints
evaluate_or(a, b, c)
evaluate_or(d, e, f)
evaluate_and(c, f, g)
# Solve the model.
solver = cp_model.CpSolver()
solver.parameters.enumerate_all_solutions = True
status = solver.Solve(model, cp_model.VarArraySolutionPrinter([a, b, c, d, e, f, g]))输出
所获得的产出如下：
Solution 0, time = 0.00 s
a = 0 b = 0 c = 0 d = 1 e = 0 f = 1 g = 0
Solution 1, time = 0.00 s
a = 0 b = 0 c = 0 d = 1 e = 1 f = 1 g = 0
Solution 2, time = 0.00 s
a = 0 b = 0 c = 0 d = 0 e = 1 f = 1 g = 0
Solution 3, time = 0.00 s
a = 0 b = 0 c = 0 d = 0 e = 0 f = 0 g = 0
Solution 4, time = 0.00 s
a = 0 b = 1 c = 1 d = 0 e = 0 f = 0 g = 0
Solution 5, time = 0.00 s
a = 0 b = 1 c = 1 d = 1 e = 0 f = 1 g = 1
Solution 6, time = 0.00 s
a = 0 b = 1 c = 1 d = 1 e = 1 f = 1 g = 1
Solution 7, time = 0.00 s
a = 0 b = 1 c = 1 d = 0 e = 1 f = 1 g = 1
Solution 8, time = 0.00 s
a = 1 b = 1 c = 1 d = 0 e = 1 f = 1 g = 1
Solution 9, time = 0.00 s
a = 1 b = 1 c = 1 d = 1 e = 1 f = 1 g = 1
Solution 10, time = 0.00 s
a = 1 b = 1 c = 1 d = 1 e = 0 f = 1 g = 1
Solution 11, time = 0.00 s
a = 1 b = 1 c = 1 d = 0 e = 0 f = 0 g = 0
Solution 12, time = 0.00 s
a = 1 b = 0 c = 1 d = 0 e = 0 f = 0 g = 0
Solution 13, time = 0.00 s
a = 1 b = 0 c = 1 d = 0 e = 1 f = 1 g = 1
Solution 14, time = 0.00 s
a = 1 b = 0 c = 1 d = 1 e = 1 f = 1 g = 1
Solution 15, time = 0.00 s
a = 1 b = 0 c = 1 d = 1 e = 0 f = 1 g = 1 页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/70571396
复制相关文章
相似问题
腾讯云开发者
