问题标签 [operations-research]

我们正在努力解决以下问题的某些方面：

• 公共交通巴士时间表包括班次（〜轨道部分），每个班次都有固定的开始和结束时间

• 公交车司机需要被分配到每个班次

• [有问题的约束]法律规定要求每位公交车司机在驾驶 4 小时后（即轮班后）有30 分钟的休息时间

• 换句话说，驾驶员在换班时累积的驾驶时间不得超过 4 小时，除非驾驶员休息 30 分钟，在这种情况下，累积的时间“重置为零”

总之，我们需要跟踪每个司机的累积驾驶时间，以抑制轮班分配以强制执行 30 分钟的休息时间。

潜在的问题似乎介于作业车间和分配问题之间：

• 像工作车间问题一样，它有许多不重叠和优先约束的班次（或任务、工作）......

• ...但是我们的轮班（~任务/工作）没有预先分配给司机；与作业车间问题相比，任务（~班次）需要在特定机器（~驱动程序）上执行，因此是预先分配的，因此分配它们不是问题的一部分

• 就像分配任务一样，我们需要将轮班分配给尽可能少的司机......

• ...但是我们还需要处理前面提到的无重叠和优先约束，在分配问题中没有考虑到这些约束

所以我的问题是，如何使用or-tools在约束问题中最好地模拟上述约束？

提前致谢！

我正在尝试使用 SciPy 解决一个非常基本的优化问题。问题受到约束并且具有可变界限，我很确定它是线性的。

当我运行以下代码时，执行失败并显示错误消息“LSQ 子问题中的奇异矩阵 C”。有谁知道问题可能是什么？提前致谢。

编辑：我将在此处添加代码应该做什么的简短描述。我在代码的开头定义了一个“需求”向量。该向量描述了在一段时间内索引的某个产品的需求。我想弄清楚的是如何下一组订单，以便在一些约束下满足这个需求。这些限制是；

• 如果在某个时间点有需求，我们必须有库存（需求指数）
• 在下订单后的 4 个“时间单位”之前，我们不能再下订单
• 我们不能在最近 4 个时间单位下订单

这是我的代码；

我有 11 支球队的 11 周比赛时间表（每周 5 场比赛）。我需要尝试从该列表中选择 11 场比赛（每周 1 场），为 11 支球队中的每支球队提供一场主场和一场客场比赛的转播。理想情况下，这将是我可以在未来几年重复使用的代码，并且如果需要，我可以扩展到更多的团队和几周。

我知道为给定的、已经创建的时间表找到可行解决方案的可能性极低，而且在许多情况下不存在解决方案。因此，当不存在上述类型的解决方案时，我想获得一个接近的时间表。也就是说，所有球队都得到两次转播，但有些球队可能会得到两场主场比赛或两场客场比赛，而不是每场比赛一场。

我看过几种不同的方法。我有许多 5x2（客队，主队）数组（每周对决），我尝试在条件下运行排序/选择（如 a_1 =\= a_j j>1 和 a_i in {1..11} ) 上，但我不知道如何让双重限制选择起作用，而且我不知道如何在没有更多可行选择时让它回到以前的选择。我试图强行使用它，但 4000 万种可能的组合超出了我的处理能力。

我正在使用 MATLab 执行所有工作。我通常可以将 C 或 C++ 转换为 MATLab 可用代码。

给定 USDA 营养素数据库：n 个向量，其中每个维度都是特定营养素，找到一组食物 F，其向量总和为 .ge。RDA 和.lt。任何毒性值。向模型添加各种其他约束，例如卡路里、质量。求解满足约束的向量的任意组合。

目前可用的网站允许一个人一次选择一种食物并建立一个“食谱”。我正在寻找一个计算解决方案。我怀疑这是一个已经有人解决的微不足道的问题。我正在寻找描述这种情况的搜索词。

“深度学习”寻找模式，但目标“模式”是输入。不涉及概率，因此很大一部分 ML 不适用。我直觉某种树遍历可能是有用的。
这是集合论和向量数学的结合。我希望存在大量的解决方案集。
我可以将输入向量设置为参数化 SQL 查询。我已经下载了 USDA 营养数据库并将其加载到 mariadb。

伪代码：从子集营养中选择 * 加入 rda_nutrs 上的营养物质.nut-1 = rda-nuts.nut-1 加入毒性营养物质.nut-1 = 毒性.nut-t1
where sum(nut-1scalar) >= rda-1scalar and sum (nut-2scalar) >=rda-2scalar {etc} and sum(nut-1scalar) <toxicity.nut1_t_scalar and sum(nut-2scalar) <toxic.nut2_t_scalar {etc}

SQL 真的可以自己解决问题吗？

我正在寻找人工建议的搜索词来查找原始信息来源。谢谢你的建议。

我目前正在评估谷歌或工具，只是注意到它本身并不是真正的求解器，而主要是与其他求解器的接口。我想知道的是这个框架使用哪些求解器来解决约束和路由问题。

我已经彻底浏览了https://developers.google.com/optimization/，但只发现

• 对于线性优化，使用 Google 的“内部开源 GLOP”
• 对于网络流优化，似乎使用了自己的求解器（“OR-Tools 在其图形库中为网络流问题提供了几个求解器。”）
• 对于混合整数编程，默认使用开源程序“COIN OR branch&cut”（但可以集成 SCIP、GLPK 和 Gurobi）

但在 CP 和 VRP 信息/指南网站上，并没有说明使用什么求解器来解决这些问题......

有没有人碰巧知道 CSP / VRP 使用了哪个求解器，或者你有没有发现我过度阅读的东西？

下面的程序（改编自http://www.hakank.org/minizinc/set_covering4b.mzn）是集合覆盖问题的解决方案（问题末尾提供的示例数据）。这运行正确。

但是，如果我替换a上面的定义：

array[ALTERNATIVES] of var set of 1..num_objects: a;

这两行在我看来是等价的：

...突然我收到以下错误：

MiniZinc：类型错误：type-in​​st 必须是 par 集，但是是 `var set of int'

这让我很困惑。我什至改变了什么？在每种情况下a都是一组整数集。在每种情况下，类型实例都是 a var set of int，但第二个会引发错误，而第一个不会出于某种原因？

这里有一些数据可以放在 .mzn 代码文件的底部，以生成一个独立的、可运行的示例：

编辑：我还添加了一个约束 1.5 来说明可能以不同的方式接近约束。

我正在尝试在 Pyomo 中为 MxN 网格上的每个 (i,j) 对编写以下约束：

到目前为止我的代码如下，我只是希望我能得到一些关于约束定义是否正确编写以满足意图的反馈。想法是6x6上的每个（i，j）单元格网格将具有以下两个约束。

此外，如果有人想回答这个问题……您如何保存计算出的 j_t+1 值以用作下一个时间段的初始值。

将记录添加到集合时，结果keys变量仅包含一个空字符串，而不是 expect "i1"。

运行该版本可能导致此问题的原因是什么Assembly GAMS.net4, Version=28.2.0.0

当我将 导出database到 .gdx 文件时，该集合包含元素i1。

我正在研究一个包含以下内容的问题：您正在驾驶一辆燃油消耗量为 m 的汽车（在我们的示例中，我们将采用 8l/100km）并且您正在驾驶长度为 x 的直道（例如：1000km）。汽车以一定量的燃料 f 启动（例如：22l）。您的汽车有一个大小为 g 的油箱（例如：55 升），并且在直道周围（例如 100 公里（1.45 美元/升）、400 公里（1.40 美元/升）和 900 公里）有加油站（每升价格） (1.22$/l). 我很难创建算法的目标是：用最少的停靠点（所以不是最便宜的路线，而是在加油站停靠最少的路线）找到最便宜的方式并告诉用户他必须在哪个加油站加油多少升以及需要多少钱。

目前使用递归和for循环（大概是O（n ^ 2））我已经创建了一种算法，可以解决某些复杂度达到一定程度的问题，当有大约100个加油站时它开始挣扎。

我的算法是如何工作的：

• 转到从一开始就可用的油箱站（示例中的 22l）
• 去每个油箱站并通过加满油箱来列出范围内的油箱站（或终点）（因为汽车可以在油箱站加油，你可以加满油箱）我确实将它保存在一个列表中，所以它不是计算了两次。
• 然后 for 循环每个可以到达的油箱站并发生递归，然后我几乎保存了所需的最少停止次数并冲洗并重复，瞧我得到最小的答案，即（在我们的示例中）停止在 100 加油10.00 升，支付 14.5 美元，然后停在 400 加油 48 升，支付 67.20 美元

我仍然存在的问题：

• 我如何（甚至可能）将复杂性降低到 O(N log N) 或线性，以便可以检查所有（即使是 100 多个加油站）。目前，递归方法下降到 10 次以上的递归，这使得该算法几乎无法解决超过 100 个加油站的任何问题。

• 目前，我的算法只加油到达下一个加油站或终点所需的燃料：如果第一个加油站比第二个加油站便宜，并且你​​可以多加油“n升，那么解决问题的最佳方法是什么？ “所以你在第二个加油站买的少了。因为在理想情况下，您在行程结束时还剩 0 升。

额外说明：

• 到达加油站的燃油为 0 升算作已经到达。
• 编辑：必须找到价格相同且站点数量最少的所有路径。

我当前的代码（片段）我认为方法名称是自我解释的，如果不是，请添加注释。，

请帮助我是否应该将以下问题建模为 VRP 或运输问题。

我要解决的问题是：

• 我有多种产品要从多个仓库运送到 2 家商店。

• 我有一个车队规模，每个仓库的车辆容量各不相同

• 我知道每个节点上每种产品的供需需求。

约束是：

• 一辆车从一个仓库到一个商店（不应该在一条路线上走多个仓库）

• 偏好来自一个来源的供应满足一家商店的全部需求，而不是聚合来自单个来源的供应。

你能帮我理解这是什么类别的问题吗？

如果我将其建模为运输问题，我如何考虑车辆的容量？我没有遇到考虑到用于运输的车辆容量的运输问题。