标签: or-tools

假设我有以下系统说明的一些变量和约束： 灰线可以拉伸和收缩它们顶部的范围给定的量。蓝线只是端点，显示了灰线如何相互作用。

我的目标：我想使用线性规划来均匀地最大化灰线的大小，如图所示。你可以想象带有弹簧的灰色线条，它们都同样向外推。一个糟糕的解决方案是将所有蓝线尽可能推向一侧。请注意，此描述中有一点余地，并且可能有多种解决方案 - 我所需要的只是让它们合理均匀，并且不要让一个值最大化压扁其他所有内容。

我尝试的目标函数只是最大化线条大小的总和：

maximize: (B - A) + (C - B) + (C - A) + (D - C) + (E - B) + (E - D) + (F - E) + (F - D) + (F - A) 

我很清楚这不是一个好的解决方案，因为这些项相互抵消，并且一条线上的增加只会在另一条线上减少相同的数量，因此目标永远不会偏向于在变量之间均匀分布最大化。

我还尝试将每条线与其中间可能范围的距离最小化。对于 line B - A，其范围内的中间值(1,3)是2。这是第一学期的目标：

minimize: |(B - A) - 2| + ...

为了实现绝对值，我将术语替换为U并添加了额外的约束：

minimize: U + ...
with: U <= (B - A - 2)
      U <= -(B …

我正在试验 F# 并希望在使用 Or-Tools 的地方进行一些约束编程。我之前曾将该包与 Python 一起使用，但我无法让它与 F# 一起使用。

我遵循 C# 示例：https : //developers.google.com/optimization/cp/cp_solver#c_5

但是在尝试添加约束时出现错误：

我是约束编程和 OR-Tools 的新手。关于问题的简要说明。有 8 个位置，对于每个位置，我需要决定应选择哪种类型 A (move_A) 的移动和类型 B (move_B) 的移动，以便从 2 个移动的组合（在每个位置）获得的值是最大化。（虽然这只是更大问题的一部分）。我想用AddElement方法来做子设置。

请看下面的尝试

from ortools.sat.python import cp_model
model = cp_model.CpModel()

# value achieved from combination of different moves of type A
# (moves_A (rows)) and different moves of type B (moves_B (columns))
# for e.g. 2nd move of type A and 3rd move of type B will give value = 2
value = [
            [ -1,  5,  3,  2,  2],
            [  2,  4,  2, -1,  1], 
            [ …

python 中的or-tools模块添加了自定义语法，其中函数可以采用任意表达式作为参数（如下所示），该语法不是立即求值，而是稍后作为约束解决

model.Add(x + 2 * y -1 >= z)

当我从函数中打印参数的类型时，它显示

<class 'ortools.sat.python.cp_model.BoundedLinearExpression'>

一种简单的方法是将表达式作为字符串传递，但感觉更好。我想了解这是如何实现的。这是在 python 中创建自定义语法的方法吗？是否需要更新解析器或类似的东西？

这是简单的程序

from ortools.sat.python import cp_model


def foo(expr):
    print(expr, type(expr))

def main():
    model = cp_model.CpModel()
    var_upper_bound = max(50, 45, 37)
    x = model.NewIntVar(0, var_upper_bound, 'x')
    y = model.NewIntVar(0, var_upper_bound, 'y')
    z = model.NewIntVar(0, var_upper_bound, 'z')
    a = 0
    b = 0
    c = 0

    model.Add(2*x + 7*y + 3*z == 50)

    solver = cp_model.CpSolver()
    status = solver.Solve(model)

    if status == cp_model.OPTIMAL:
        print('x value: ', …

我的团队正在构建一个 CP-SAT 求解器，该求解器可以在一段时间内安排作业（例如家庭作业），并且可用性可变（可用于完成作业的时间）。我们正在努力加速我们的模型。

我们尝试了 num_search_workers 和其他参数调整，但想检查其他速度的提高。目标是在 5-10 秒内解决约 100 天的问题和最多 2000 个作业（以 M1 mac 为基准）。有任何想法吗？

问题描述：按照这些要求在 d 天内布置作业

• 一天的分配时间不得超过当天的可用时间
• 应尊重赋值依赖性（如果 A 需要 B，则 B 不应出现在 A 之后）
• 作业可以分开（以便更好地适应时间很少的日子）
• 针对一天中任务类型的多样性进行优化

# 天和 # 个作业后，解决问题的速度显着减慢。这是预料之中的，但我们想知道您是否可以提出可能的加速建议

这是一个单元测试示例。希望能够展示拆分、排序和时间限制。

days = [{"secondsAvailable": 1200}, {"secondsAvailable": 1200}, {"secondsAvailable": 1200}, {"secondsAvailable": 1200}]
assignments = [
    {"id": 1, "resourceType": "Type0", "seconds": 2400, "deps": [], "instances": 2},
    {"id": 2, "resourceType": "Type0", "seconds": 1200, "deps": [1], "instances": 1},
    {"id": 3, "resourceType": "Type0", "seconds": 1200, "deps": [1, 2], "instances": 1},
    ]
result …

我正在尝试使用 OR-Tools 中的 MinCostFlow 解决工程问题。有一个带有管道和多个供应阀的机械分配系统。这些阀门需要连接到消费者。最初，我试图用匈牙利算法来解决这个问题，但后来我意识到通过路径的流量没有被考虑在内。

我用这样的最小成本流对问题进行了建模：

节点 0-4 是消费者，节点 4-7 是供应阀，节点 8 和 9 是管道。我在每个消费者身上放置了一个“供应”，以显示它期望的流量。我在最后放了一个水槽，以便从系统中取出电源。并非所有消费者都有相同的需求。我们可以看到节点 0 需要 10 个，我专门设计了一条路径（以红色突出显示），允许它携带它到那里。我暂时将所有价格设置为 0。

我希望它能像这样解决这个系统：

然而，它实际上是这样解决的：

出于某种原因，它决定将节点 0 拆分为 2 个节点（6 和 7），然后让较大的节点 7 从 3 和 0 接收 5。从系统角度来看，这并不理想，我不明白为什么会这样会这样解决。在匈牙利算法中，它不允许一个 Worker 接受多个 Job。在该算法中，节点 4-7 将是工人，而 0-3 将是作业。

我可以通过增加从节点 1-3 到节点 7 的弧的成本来获得所需的结果，但我不想操纵成本字段来获得所需的结果。这似乎需要很多额外的工作来帮助优化工具选择正确的路径。

我如何使用 OR-Tools 来完成此操作？

我正在探索 Google 的 Cp-SAT 来模拟特定类型的约束，如下所示：

约束：

变量 X 可以取值为 1、2 和 3
变量 Y 可以取值为 2、3 和 4
变量 Z 可以取值为 5、6 和 7
当变量 X 值为 1 时，则 Y 只能
取值为3 或 4当变量 Y 值为3，那么Z只能假设为7

给定变量 Y 值是 3 而 Z 值不是 7，找出 X 和 Z 的可能值。

我无法使用 Google 的 CP-SAT java 接口对此进行建模。任何人都可以帮忙吗？

我探索了以下示例，但仍然无法弄清楚：https : //github.com/google/or-tools/blob/stable/ortools/linear_solver/samples/LinearProgrammingExample.java

https://github.com/google/or-tools/blob/stable/ortools/linear_solver/samples/SimpleMipProgram.java

对于我的论文，我正在制作一个简单的时间表模型。下面可以找到一小部分代码。该模型旨在根据时间 t 所需的工作量将一组专业工人连接到一个班次。目前，这只是一个纯粹的满意度问题。

模型：

enum employees; % all employees
set of employees: runnersPrimary; % runners employees
array[positions] of float: positionsRatio; % 50% of workload should be runners

% General labels
enum positions = {bar, runner, kitchen, free};
set of employees: emergencyResponseOfficer;

% Contract hours
array[employees] of int: contractHours;

% Workload requested
set of int: shiftLength = 1..(7*24); % one week schedule, scheduled per hour
array[shiftLength] of int: workload;

% Settings
int: minShiftLength = 3;
int: maxShiftLength = 8;

% Target …