标签: or-tools

我是约束编程的初学者，我在我的 c# 程序中使用Google or-tools 库。

我想向我的求解器添加以下约束：

((t1 >= 12 && t1 <= 15) || (t2 >= 16 && t2 <= 18)) && ( t1 + t2 ) < 30

所以我用c#写了下面一段代码：

var solver = new Solver("My_CP_Colver");
var t1 = solver.MakeIntVar(12, 20,"t1");
var t2 = solver.MakeIntVar(12, 20,"t2");

solver.Add(???)//<-((t1 >= 12 && t1 <= 15)||(t2 >= 16 && t2 <= 18)) && ( t1 + t2 ) < 30

请帮助做出上述限制？

我正在尝试解决具有时间窗口限制的 TSP。我正在评估以下工具。

1. OptaPlanner - 由 Jboss 社区支持。不是特定于 TRP 的，而是通用约束求解器引擎。

2. Jsprit - 不确定它的支持。它是由 GraphHopper 开发的吗？它在 GitHub 上列出了 Graph Hopper 的子项目之一。

3. Google OR 工具 - 它是用 C++ 编写的。但可以在java中运行。

上述每种工具的优点和缺点是什么？市场上有更好的开源/付费工具吗？

我正在使用 OR-Tools 约束编程工具解决几何问题。

你们中的一个人能告诉我创建自定义约束的过程吗？我真的不明白恶魔，模型访客的行为......

另外，可以插入任何类型的约束吗？

先感谢您

我正在为 Job-Shop 问题实施一个类似的解决方案，但有一个区别：我不知道必须执行每项任务的机器。解决这个问题也是问题的一部分。事实上，我们可以说，我正在尝试解决护士问题和工作车间问题的组合。

更具体地说，我有一些持续时间为 D 的任务 T，由于他们的性质 N（假设前端任务、后端任务等），这些任务必须由某些特定员工 E 以特定顺序 O 执行。

我有：

• 可以获取 E 范围内的值的 T int vars 数组（将要执行任务的员工）。
• 一组固定的持续时间间隔变量（以知道它的持续时间 D 来安排它们）。
• E 序列变量，它应该是员工将要执行的任务序列（间隔变量）。
• 任务和员工之间关系 N 的一些约束。
• O 阶的一些其他约束。

解决这个问题的一种方法是：先解决分配问题，然后安排任务。我已经做到了这一点。

但是我想将它作为一个独特的解决方案来实现。

我被困在这个：如何创建一个依赖于我之前创建的 int vars 的析取约束？

对于那些需要查看代码的人：

for i in range(number_employees):
    disj = solver.DisjunctiveConstraint([interval_var[task_id] if int_var[task_id] == i] ,'i_name')
   [...]

当然，那是行不通的。

我真的很感激任何建议。

对于 or-tools 中的 VRP，有没有办法让车辆在某些固定位置开始，但允许任意结束位置？

文档https://developers.google.com/optimization/routing/routing_tasks#setting-start-and-end-locations-for-routes和https://developers.google.com/optimization/routing/routing_tasks#allowing-任意开始和结束位置显示如何分别设置自定义或任意开始/结束位置。

我的问题是我们可以将它们结合起来吗？即自定义开始位置和任意结束位置（反之亦然）？

谢谢

我正在使用 Google OR-Tools 在几天内优化单个车辆的路线。

我在尝试着：

• 能够指定优化路由的天数。
• 能够指定每天的开始位置和结束位置。
• 能够指定每天的开始时间和结束时间。

我有一组 40 个位置。对于我想包含在我的优化天数范围内的每一天，我将开始和结束位置添加到矩阵中。所以如果我想优化一天，我的矩阵中总共会有 42 个位置。如果我想优化两天，我的矩阵中总共会有 44 个位置。等等。模式是这样的：

1 Day:
Matrix = [[start day 1], [end day 1], [location], [location], ... ]

2 Days:
Matrix = [[start day 1], [end day 1], [start day 2], [end day 2], [location], [location], ... ]

3 Days:
Matrix = [[start day 1], [end day 1], [start day 2], [end day 2], [start day 3], [end day 3], [location], [location], ... ]

我希望允许删除位置以实现可行的解决方案，并且只允许在指定的时间窗口内访问位置，我相信我已经成功实施了这两个选项。

我当前的实现可在此处以及GitHub 上找到。 …

在 Docker 中，我尝试运行 pip install ortools 但找不到。其他 pip 安装包可以完美运行。我在 Dockerfile 中使用“FROM python:3.6.8-alpine”

bash-4.4# pip install ortools
Collecting ortools
  ERROR: Could not find a version that satisfies the requirement ortools (from versions: none)
ERROR: No matching distribution found for ortools


bash-4.4# pip install --upgrade pip
Requirement already up-to-date: pip in /usr/local/lib/python3.6/site-packages (19.1.1)

根本原因： Gooogle OR 工具不支持 alpine，因为 alpine 不支持 pypi

关注此问题的进展：https://github.com/google/or-tools/issues/756

我要解决的问题有点像员工在这里安排：

https://github.com/google/or-tools/blob/master/examples/python/shift_scheduling_sat.py

但是，有些事情我仍然坚持，不知道如何将其合并到代码中。我将在下面解释问题。

问题

我有47列火车的车队，我想每天分配给49条路线。应该为火车分配以下约束：

1. 每天至少必须使用每趟火车一次（整天都不得闲置火车）

2. 必须将每列火车分配到至少一条路线（最多两条路线），并且必须覆盖每条路线

3. 分配给路线的火车最终里程不得超过24,800（即前一天的累积里程+分配的路线里程<= 24,800）。通过查看下面第三张表中的total_km_day_end列，可以最好地理解这一点

4. 如果一天中将火车分配给两条路线，则两条路线的时间不得重叠

我想拥有一个进一步的约束，但是这并不珍贵（这是一个软约束）：

5. 前一天行驶里程高的火车应该分配到短途，前一天行驶里程低的火车应该分配到长途

我有一个像这样的火车数据框。我可以随机选择一个日期，并查看47列火车中每列火车直到前一天（即2018年9月18日）结束时的累积里程：

Date      |  Day      |   Train   |  Cum_mileage_prev_day 
----------| --------- | --------- |----------------------  
19/9/18   |  WED      |   T32     |  24,300          
19/9/18   |  WED      |   T11     |  24,200
19/9/18   |  WED      |   T38     |  24,200       
 .          .               .         .            
 .          .               .         .            
19/9/18   |  WED      |   T28     |  600  
19/9/18   |  WED      |   T15     |  200   
19/9/18   |  WED      |   T24     |  100  

路由的数据框如下所示。请注意，高于100公里的路线被定义为长路线，低于此路线则为短路线。在这49条路线中，只有6条短路线（10公里）-请注意，以下仅显示了5条短路线：

Route …

我正在尝试找出如何从 中获取可能解决方案的完整列表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 工具的文档，而且我似乎忘记的东西比我想象的要多得多。