标签: cp-sat

我有一个列表Employee和一个列表Mission。每个任务都有开始时间和持续时间。

在CP模型（谷歌CpSat，从或工具包），我定义shifts = Dictionary<(int,int),IntVar>，其中shifts[(missionId, employeeId)] == 1当且仅当这个任务是由这名员工来实现。

我需要将每个任务分配给一名员工，显然一名员工无法同时完成两项任务。我已经写了这两个硬约束，它们运行良好。

问题：

现在，有些任务是“链接”在一起的，应该由同一个员工来实现。它们存储如下：

linkedMissions = {{1,2}, {3,4,5}}

在这里，任务1和任务2必须由同一个员工共同实现，任务3、4和5也是如此。

为了编写这最后一个约束，我为每个员工收集了应该链接在一起的所有班次的列表，然后我让它们都相等。

foreach (var employee in listEmployeesIds)
foreach (var missionGroup in linkedMissionsIds)
{
    var linkedShifts = shifts
        .Where(o => o.Key.Item2 == employee
                    && missionGroup.Contains(o.Key.Item1))
        .Select(o => o.Value)
        .ToList();

    for (var i = 0; i < linkedShifts.Count - 1; i++) 
        model.Add(linkedShifts[i] == linkedShifts[i + 1]);
}

然而，求解器告诉我该模型不可行，但我可以用纸和笔轻松找到工作计划。我有 35 名员工和 25 个任务，连接在一起的任务不重叠，所以应该没有任何问题。

编辑：

作为替代方法，正如@Laurent Perron 所建议的，我尝试对所有必须在一起的班次使用相同的布尔变量：

var constraintBools = new …

我正在使用 CP-Sat 求解器来优化我正在制定的时间表。然而，现在这个问题需要很长时间才能解决。是否可以用旧结果为求解器提供种子，作为起点，以减少找到最佳结果所需的时间？

我正在尝试找出如何从 中获取可能解决方案的完整列表ortools.sat.python.cp_model。我知道我可以打印它们，如下例所示，但我不清楚如何获取这些值，例如作为嵌套列表或字典列表。我尝试通过修改 并将解决方案附加到列表属性来编写自己的回调类VarArraySolutionPrinter，但由于某种原因，这始终导致 python 内核崩溃。无论如何，必须有更直接的方法。我不认为解析打印输出是一个选项。

from ortools.sat.python import cp_model

model = cp_model.CpModel()

x00 = model.NewBoolVar('x00')
x01 = model.NewBoolVar('x01')
x02 = model.NewBoolVar('x02')

model.AddBoolOr([x00, x01, x02.Not()])
model.AddBoolOr([x00.Not(), x02.Not()])

# Create a solver and solve.
solver = cp_model.CpSolver()
solution_printer = cp_model.VarArraySolutionPrinter([x00, x01, x02])
solver.SearchForAllSolutions(model, solution_printer)

## Prints:
Solution 0, time = 0.00 s
  x00 = 0   x01 = 1   x02 = 0 
Solution 1, time = 0.01 s
  x00 = 0   x01 = 0   x02 = 0 
Solution 2, …

我正在重新使用 Google 的 OR 工具并尝试（相对）简单的优化。我正在使用 CP SAT 求解器，但我可能在这里遗漏了一些基本内容。我有一些变量 x、y 和一些常量 c。如果 y 小于 c，我希望 x 等于 1，否则等于 0。

from ortools.sat.python import cp_model

solver = cp_model.CpSolver()
model = cp_model.CpModel()
c = 50
x = model.NewBoolVar(name='x')
y = model.NewIntVar(name='y', lb=0, ub=2**10)

model.Add(x == (y < c))

model.Maximize(x+y)

status = solver.Solve(model)

我收到一条错误消息

TypeError: bad operand type for unary -: 'BoundedLinearExpression'

看来我在这里滥用 OR 工具语法来限制我的约束。我很难理解在线 OR 工具的文档，而且我似乎忘记的东西比我想象的要多得多。

我正在尝试使用以下方法生成自动化文档：
mkdocs = "^1.4.2"
mkdocstrings = "0.19.0"
mkdocs-material = "8.5.8"
mkdocstrings-python = "0.7.1"

我的 mkdocs.yml 看起来像这样：

site_name: Optimization Services Documentation
site_url: "https://example.com"

theme:
  name: "material"
nav:
  - 'index.md'
  - 'reference.md'
plugins:
  - search
  - mkdocstrings:
      handlers:
        python:
          setup_commands:
            - import sys
            - sys.path.append('../')
          selection:
            new_path_syntax: true

index.md 仍然是 mkdocs new 生成的默认文件。

Reference.md 看起来像这样：

# Reference
::: modelling.constraints

和 modelling.constraints.py：

def init_constraints(groupes_chantiers: list[GroupeChantiers],
                     digraph_precedence: nx.DiGraph,
                     graph_coactivite: nx.Graph,
                     model: cp_model.CpModel,
                     **kwargs) -> None:
    """
    Adds constraints to cp_model
    Args:
        groupes_chantiers: 
        digraph_precedence: 
        graph_coactivite: …

我有一个优化问题，我有一个“BoolVar”对象列表的列表。所以像这样：

[[BoolVar1,BoolVar2],[BoolVar3, BoolVar4],[BoolVar5,BoolVar6]]

我需要评估以下内容：

(BoolVar1 && BoolVar2) || (BoolVar3 && BoolVar4) || (BoolVar5 && BoolVar6)

我是否必须按如下方式执行此操作：

and12 = model.NewBoolVar("and12")
model.Add(and12 == True).OnlyEnforceIf([BoolVar1,BoolVar2])
and34 = model.NewBoolVar("and34")
model.Add(and34 == True).OnlyEnforceIf([BoolVar3,BoolVar4])
and56 = model.NewBoolVar("and56")
model.Add(and56 == True).OnlyEnforceIf([BoolVar5,BoolVar6])
model.AddBoolOr([and12,and34,and56])

我已经尝试过这段代码，它似乎有效，但由于“OnlyEnforceIf”功能，我对此表示怀疑。如果不强制执行会怎样？那么 and12 是否设置为 False，或者可以是 False 或 True，因为此后该等式不再强制执行？我根据这篇文章找到了这段代码。

我有一组U用户和一组S服务器。我想最大化分配给服务器的用户数量，同时最小化使用的服务器数量（这意味着我有两个目标函数）。

每个用户都有一些需求w ，每个服务器的总容量为C。

求解器变量如下：

# x[i,j] = True if user u[j] is allocated to server s[i]
# x[i,j] = False otherwise

# y[i] = True if server s[i] is used to serve users
# y[i] = False otherwise

如前所述，我想最大化x[i,j]，同时最小化y[i]

限制如下：

• 容量约束：由于每台服务器i都有一定的容量，因此分配的j个用户不得超过该容量
• 邻近约束：只有位于服务器范围内的用户才能分配给它。一个用户可以位于多个服务器的重叠范围内
• 约束系列：确保每个用户最多分配到一台服务器。

使用这个库

from ortools.sat.python import cp_model

到目前为止我已经做了：

• 创建求解器变量（它们是布尔值）
• 创建约束
• 最大化 x[i,j] 变量
• 获取目标函数

例如，如果我有 10 个用户和 4 台服务器，则所有 10 个用户都分配到 4 台服务器中

我需要但未能完成的事情：

• 最大化x[i,j] …

在谷歌 OR-tools 库中，“原始”CP-Solver（此处讨论： https: //developers.google.com/optimization/cp/original_cp_solver）可以使用重新播种.ReSeed()。然而，较新的版本，CP-SAT 不能。

我的假设是 CP-SAT 将详尽地尝试您问题中的每个选项，从可行的选项中选取最大值或最小值（取决于您的优化目标）。因为它会尝试所有这些，所以不需要做种，因此该选项对您不可用。

这种理解正确吗？如果是的话，为什么原始求解器有种子？.ReSeed()如果我的说法不正确，那么新 CpSolver 中缺少 是否是一个疏忽？

设置

我使用 google OR 工具作为约束编程求解器：

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：我无法立即在网上找到此信息，但根据我在此处的相关问题和此处另一个人的另一个相关问题上得到的答案找到了解决方案。我以问答的形式总结了我的发现，希望它们对某人有用。

我是数据挖掘领域的博士候选人，我必须使用 ORtools 创建一个全局约束以用于数据挖掘目的。

问题是互联网上缺乏关于使用 CP-Sat 创建自己的全局约束的文档，我不知道如何开始。