或工具不遵守约束

Question

我有这个简单的 CP 程序：

from ortools.sat.python import cp_model
horizon = 5
model = cp_model.CpModel()
A = model.NewIntVar(1, horizon, 'A')
C = model.NewIntVar(1, horizon, 'C')
D = model.NewIntVar(1, horizon, 'D')
E = model.NewIntVar(1, horizon, 'E')
model.Add(max(A+C+D, A+D+E) > max(A+C+E, C+E+D))
solver = cp_model.CpSolver()
status = solver.Solve(model)
if status in (cp_model.FEASIBLE, cp_model.OPTIMAL):
    print('status: ', status)
    print('A: ', solver.Value(A))
    print('C: ', solver.Value(C))
    print('D: ', solver.Value(D))
    print('E: ', solver.Value(E))
else:
    print('Could not solve')

和运行它给了我：

status:  4
A:  5
C:  1
D:  1
E:  1

考虑到所提供的约束，这是不正确的。我做错了什么吗？

Answer 1

您不能将 min、max、or、and 与 ortools 变量一起使用，因为它们会覆盖 __ge__、__lt__ 创建线性表达式的魔法方法。

在这种情况下，您必须创建 4 个新变量（每个总和 1 个）和另外 2 个受 model.AddMaxEquality 约束的变量。您也可以使用 2 个布尔值来设置 2 个最大变量。

编辑：

acd = model.NewIntVar(1, 3 * horizon, "ACD")
model.Add(acd == A + C + D)
ade = model.NewIntVar(1, 3 * horizon, "ADE")
model.Add(ade == A + D + E)
ace = model.NewIntVar(1, 3 * horizon, "ACE")
model.Add(ace == A + C + E)
ced = model.NewIntVar(1, 3 * horizon, "CED")
model.Add(ced == C + E + D)

max1 = model.NewIntVar(1, 3 * horizon, "max1")
max2 = model.NewIntVar(1, 3 * horizon, "max2")
model.AddMaxEquality(max1, [acd, ade])
model.AddMaxEquality(max2, [ace, ced])
model.Add(max1 > max2)

Answer 2

根据斯特拉迪瓦里的回答郑重声明：

#!/usr/bin/env python3
from ortools.sat.python import cp_model
horizon = 5
model = cp_model.CpModel()
A = model.NewIntVar(1, horizon, 'A')
C = model.NewIntVar(1, horizon, 'C')
D = model.NewIntVar(1, horizon, 'D')
E = model.NewIntVar(1, horizon, 'E')

#model.Add(max(A+C+D, A+D+E) > max(A+C+E, C+E+D))
acd = model.NewIntVar(1, 3 * horizon, "ACD")
model.Add(acd == A + C + D)
ade = model.NewIntVar(1, 3 * horizon, "ADE")
model.Add(ade == A + D + E)
ace = model.NewIntVar(1, 3 * horizon, "ACE")
model.Add(ace == A + C + E)
ced = model.NewIntVar(1, 3 * horizon, "CED")
model.Add(ced == C + E + D)

max1 = model.NewIntVar(1, 3 * horizon, "max1")
max2 = model.NewIntVar(1, 3 * horizon, "max2")
model.AddMaxEquality(max1, [acd, ade])
model.AddMaxEquality(max2, [ace, ced])
model.Add(max1 > max2)

solver = cp_model.CpSolver()
status = solver.Solve(model)
if status in (cp_model.FEASIBLE, cp_model.OPTIMAL):
    print('status: ', status)
    print('A: ', solver.Value(A))
    print('C: ', solver.Value(C))
    print('D: ', solver.Value(D))
    print('E: ', solver.Value(E))

    print('ACD: ', solver.Value(acd))
    print('ADE: ', solver.Value(ade))
    print('max1: ', solver.Value(max1))

    print('ACE: ', solver.Value(ace))
    print('CED: ', solver.Value(ced))
    print('max2: ', solver.Value(max2))
else:
    print('Could not solve')

可能的输出：

%./max.py
status:  4
A:  2
C:  1
D:  2
E:  1
ACD:  5
ADE:  5
max1:  5
ACE:  4
CED:  4
max2:  4

或工具不遵守约束

Constraint is not respected by or-tools

or-tools