问题标签 [or-tools]

For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.

0 投票
2 回答
1496 浏览

linear-programming - 在 Google or-tools 中获取所有解决方案

我有一个线性问题,即找到满足所有约束的所有解决方案。例如,我的变量是 = [0.323, 0.123, 1.32, 6.3...] 是否可以获得例如按适应度(最大化/最小化)函数排序的前 100 个解决方案?

0 投票
1 回答
367 浏览

or-tools - 谷歌优化工具python中两个变量的乘积

我有一个优化问题。目标是最大化两个变量 x 和 y。如何在谷歌优化工具python版本中表示它。

我现在能做的是:

0 投票
1 回答
1597 浏览

python - OR-tools 始终返回非常次优的 TSP 解决方案

生成一些随机高斯坐标,我注意到 TSP 求解器返回可怕的解决方案,但是它也一遍又一遍地返回相同的可怕解决方案对于相同的输入。

鉴于此代码:

例如,对于 10 分,我得到了一个很好的解决方案:

在此处输入图像描述

对于 20 更糟糕的是,仍然存在一些明显的优化(其中一个只需要交换两个点。

在此处输入图像描述

而对于 200 来说,这太可怕了:

在此处输入图像描述

我想知道上面的代码是否真的做了一些 LNS,或者只是返回初始值,特别是因为大多数first_solution_strategy选项都建议确定性初始化。

为什么上面的 TSP 求解器会为相同的数据返回一致的解,即使禁忌搜索和模拟退火等是随机的。而且,为什么 200 分解决方案如此糟糕?

我在 SearchParameters 中使用了几个选项,尤其是在local_search_operators. 这没有任何效果,返回了同样非常次优的解决方案。

0 投票
1 回答
1782 浏览

python - 在存在顺序约束的情况下,OR-tools 路由无法找到“微不足道”的最佳解决方案

为了更好地理解 or-tools 路由背后的约束编程,我创建了一个 depot 和 4 个其他节点的玩具示例,配置为允许两条路由。

在此处输入图像描述

这个想法是,车辆从仓库行驶01,然后选择23,继续前往4并返回仓库0;车辆选择绿色或红色路径。我的实际问题更复杂,有多辆车,但有类似的限制。

对于这个例子,我为成本创建了一个欧几里德距离函数:

还有一个 l0 距离函数来约束顺序:

然后我创建模型并尝试解决这个问题:

因此[1][4]析取允许ALL_UNPERFORMED第一个解决方案起作用,析取[2, 3]表明应该选择绿色或红色路径。

通过这些析取,求解器找到了一个解决方案,但如果我添加它2 并且3应该在 after1和 before访问4,求解器不会访问2或根本不会访问3。为什么会这样?为什么求解器不能找到0 -> 1 -> 2/3 -> 4 -> 0避免int(1e10)析取惩罚的更优路径[2,3]

编辑:

通过删除它们并添加到来软约束顺序约束Distance.__call__

惩罚一个不允许的命令,导致路由0 -> 2 -> 1 -> 4 -> 0。所以我想知道为什么 or-tools 不会交换1and 2,即使在明确启用use_swap_activeanduse_relocate_neighbors时也是如此search_parameters.local_search_operators

注意:失败是因为它应该是:

结论:搜索空间很小,更好的解决方案在use_relocate_neighbors返回的解决方案附近,但 or-tools 没有找到它。为什么?

所有代码:

0 投票
2 回答
1396 浏览

amazon-web-services - How to install Google or-tools on AWS Lambda?

I've been successfully using Google's or-tools on AWS EC2 instances but have recently been looking into including them in AWS Lambda functions but can't get it to run.

Function debug.py

Below is just a basic function importing the pywrapcp from ortools which should succeed if everything is set up correctly.

Failing Module Import

I created a package.sh script that copies all dependencies to the project following Amazon's instructions before creating a zip archive. Running the deployed code results in this:


Contents of package.sh

When I copy the ortools folder from ortools-4.4.3842-py2.7-linux-x86_64.egg directly into the project root it finds ortools but then fails to import pywrapcp which may be related to a failure loading the native libraries but I'm not sure since the logs don't show much detail.

Any ideas?

0 投票
4 回答
414 浏览

python - 从源代码安装 Google or-tools 时使第三方无法运行 - Windows

总的来说,我对 Python 编程和开发相对较新,所以我很惊讶地发现我在安装 Google or-tools时很幸运。也就是说,直到这个命令:$ make third_party. 该命令无法识别:

如果我移动到文件tools所在的子目录,make.exe则可以识别该命令,但会产生错误:

现在我完成了沿途的每一步(安装了 CMake 和 Java JDK 等),包括将 GLPK 和 SCIP 添加到依赖项,并将所有可执行文件添加到我的PATH.,添加来自 VS2015、CMake 和 TortoiseSVN 的 bin尽管 Google 的说明没有明确说明,但我还是安装了。

我知道 SVN 应该与Makefileor-tools 存储库中的 接口,但它似乎无法识别它 - 选择 TortoiseSVN 而不是另一个选项可能是什么?我究竟做错了什么?

Microsoft Visual Studios 2015 的工具菜单中也没有终端 - 他们是否要求我使用 VS2015 的开发人员命令提示符?

0 投票
0 回答
3929 浏览

java - Optoplanner vs jsprit vs Google OR 工具

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

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

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

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

上述每个工具的优点和缺点是什么。市场上有没有更好的开源/付费工具?

0 投票
1 回答
350 浏览

c# - orTools 如何从 RoutingModel 获取状态?

我正在使用下面的代码设置 routingModel 的时间限制。

但是我不知道搜索完成后如何获取状态,所以我可以检查是否是时间限制取消它或由于其他原因没有找到解决方案。请帮忙

RoutingModel 类具有此静态属性,但我不知道如何从实例中读取它们:

0 投票
1 回答
936 浏览

c# - 谷歌 ortools - 有容量的车辆路由 pb

以下代码的问题是:

即使我只有 10 个要交付的位置,并且在位置 0 设置了一个站点,在此示例中,车辆 1、2、3、4 似乎在位置 10、11、12、13 有它们的站点。这些位置不存在。我拥有的 10 是从 0 到 9 编号的。

另一方面,业务逻辑似乎还可以:

当我分离出离开仓库的成本和返回仓库的成本(值 10)时,我得到了预期的结果:104。城市之间只有 4 次不包括仓库的旅行。

这是 Google or-tools 中的错误吗?

在此处输入图像描述

0 投票
2 回答
1528 浏览

python - N-Queens 对称性破坏 Google OR 工具

Google or-tools 的示例之一是 n-queens 问题的求解器。 在底部,它说可以通过向约束求解器添加对称破坏约束来改进实现。

环顾互联网,我发现了 n-queens 问题的对称破坏约束,但我一生都无法弄清楚如何将这些约束转换为实现它们的 python 代码。


编辑:这是一个糟糕的问题,让我们更新......

我尝试了什么?

这是上面第一个链接的设置:

我知道我可以成功实现简单的约束。如果我想确保解决方案在第一行的第一列中始终有一个皇后,我可以这样实现:

queens[0]变量表示第一列中的皇后位置,并且仅当第一列在第一行中有皇后时才满足此约束。然而,这当然不是我想要做的,因为解决方案可能不包含任何角落单元格。

n-queens 问题的对称破缺约束如下所示。它们是直接从第二段中的链接中提取的。

n-皇后对称破缺约束

我了解这些约束是如何工作的。这个想法是,您可以将此函数应用于 n-queens 板上的每个单元格,以便将状态转换为等效状态。这些状态之一将是该状态的规范表示。这被用作通过消除重复评估来修剪未来处理的方法。

如果我只是以事后的方式实现这一点,我会完全按照我上面描述的那样做,使用每个可能的对称破坏函数转换状态,计算某种状态散列(例如,每列中选定行的字符串)并为每个建议的解决方案选择最低的一个。跳过我们以前见过的未来处理。

我的问题是我不知道如何将这些转换转换为 google or-tools 约束编程求解器的约束。

让我们看一下d1(r[i] = j) => r[j] = i关于主对角线的最简单的反射。我所知道的是,需要将转换应用于所有单元格,然后与当前状态进行比较,以防止一个单元格被扩展。我对 python 的了解不够,无法理解哪种表达式适用于转换,我只是不知道如何创建将转换与此特定求解器的当前状态进行比较的约束。