问题标签 [operations-research]
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.
python - CP-SAT:较高的 num_search_workers 值会增加解决时间
亲爱的,
我正在使用num_search_workers参数,我发现在 Windows 上使用 or-tool 7.5 时出现了一个奇怪的行为。
我在 32 核机器上做了以下测试,发现 1 个线程的性能最好。
你知道为什么吗?:
开始使用 1 个线程解决...在 13.578 秒内解决
开始使用 2 个线程解决...在 45.832 秒内解决
开始使用 4 个线程解决...在 53.031 秒内解决
开始使用 8 个线程解决...在 62.013 秒内解决
开始使用 16 个线程解决...在 157.5 秒内解决
开始使用 32 个线程解决...在 807.778 秒内解决
开始使用 64 个线程解决...在 386.252 秒内解决
该模型或多或少类似于以下内容:
考虑 self.suggested_decisions 是 BoolVars (决策变量)的字典问题如下:
or-tools - Cp-Sat AddAllDifferent 与添加约束
亲爱的,
我有一个有两个布尔决策变量的模型,只有一个可以等于 ti 1。
如果我使用 AddAllDifferent 或者我使用简单约束 (ADD) x+y=1,它的求解器会更快吗?
linear-programming - 我的代码有什么错误?我还没有设置数据
我试图在 cplex 中解决这个运输问题 在此处 输入图像描述
这是我的 OPL 代码
诠释 p=...;
诠释q=...;
范围 i=1..p;
浮动一个[i];
范围 j=1..q;
浮动 b[j];
浮动 c[i][j];
dvar 布尔值 x[i][j];
最小化 sum(l in i,m in j)x[l][m]*c[l][m];
受{
forall (l in i) sum(m in j) x[l][m] <= a[l];
forall (m in j) sum(l in i) x[l][m] >= b[m];
}
在此处输入图像描述 这是我的 .dat
我不断收到此错误“数据元素“a”已设置”。
image - 计算文档图像中的白斑度量
论文'基于度量的异构文档图像的无参考质量评估'讨论了测量文档图像中字符的质量。我很难理解第 7 页中的白斑度量。
小白斑测量加粗的字符笔划缩小了字符内部现有的白色连接组件,或者通过连接字符笔划创建了新的组件。计算文档图像中白色连通分量的直方图,我们已经找到了最常见的字体大小。然后通过将 1 像素和 1% 字体大小平方之间的直方图 bin 相加来计算白色斑点。然后通过除以 1 和字体大小平方之间的直方图下面积来归一化总和。
我的问题是:
- 如何计算文档图像中白色连通分量的直方图?
- 如何通过将 1 像素和 1% 字体大小平方之间的直方图 bin 相加来计算白色斑点?例如,最常见的字体大小是 32,所以我必须将直方图 bin 1 的频率加到 32^2 (1024) 的百分之一?那正确吗?
- 老实说,我没有看到计算或总结 1 像素和 1% 字体大小平方之间的直方图箱的任何关系 small
white speckle measure
。你能帮我看看关系吗?
谢谢。
algorithm - 如何改进用于作业调度的 SA 算法?
代码在上面。
我的工作安排有问题。我的启发式算法使用 possible_solution 矩阵将每个作业分配到一行。例如,第 6 个工作有 140 个不同的选项,第 7 个工作在 possible_solution 矩阵中有 30 个不同的选项。
在模拟退火中,在每次迭代中,我随机使用其中一条解线进入 possible_solution 矩阵。但是,与 GAMS/Cplex 求解器相比,该解最多达到 50%。
我可以使用解决方案矩阵中的随机选择来使用模拟退火吗?我错过了什么?
algorithm - 如何为模拟退火生成邻居?
我有 61 个工作,我想在一些限制条件下最大化他们的 delay_savings。
当我运行算法时,结果如下:
这是算法的初始解。之后我应该如何继续算法?我的意思是我将如何以及在何处使用此结果来获得更好的 SA 解决方案?
你能给我写一个伪代码吗,你可以在你的伪代码建议中将上面的算法定义为“initial_algorithm”。我绝对无法将其修改为模拟退火并构成邻居以让步SA算法以逐渐达到更好的结果。
我是随机制作的,但它离 SA 过程逻辑有点远。所以,我在这里:)
Edit1:我使用这个算法:
我在每次迭代中生成 currentSolution 重新运行 getnewSolution,它不会进入任何东西,随机工作。我知道这是本地搜索的问题。然而,它接近 GAMS/Cplex 结果的 80%。
但是,随机性并不意味着逐渐改善。那么,如何使用第一个算法结果来获得更好的 SA 解决方案?
我尝试选择 30 个工作并确定他们的 delay_savings 在约束条件下可能发生变化的下限和上限。我将在每次迭代到 SA 中时为它提供邻居算法。它是否提供了邻居解决方案,还是我错过了关于模拟退火过程的一些内容?
algorithm - 基于用户约束的锦标赛时间表创建算法
我代表我的一个朋友经营一个网球网站,因为她对技术和计算机并不是那么热情。
当我们创建锦标赛订阅页面时,用户和业余网球运动员填写表格以订阅该锦标赛。
表单中有一个字段,用户可以根据需要描述他们的可用性。
基本上,用户会写他们什么时候可以参加比赛,而且大多数时候他们是时间约束,例如:
“晚上9点以后我可以玩所有晚上”,“只能在工作日”,“因为工作,我只能在周末玩”,“总是,除了不能每天晚上10点之后,因为我要早起”。
我称它们为时间约束。
昨天我发现了一个新的约束,它是这样的:
“我(用户A)和我的朋友(用户B)为了参加比赛将共享汽车,因为我们住的地方离你很远,而且我们要长途跋涉,我们想聚在一起以节省燃料。只要我的朋友在比赛中没有被淘汰,我宁愿和我的朋友(userB)在相似的时间玩。如果我的朋友被淘汰了,我每次都可以玩”
我现在的问题是,是否有一种算法可以满足所有这些约束,或者我的朋友即使不是技术人员或极客也可以使用的预先准备好的解决方案。
我知道这个算法应该在每天之后运行,因为当然比赛获胜者事先并不知道,因此用户时间成本限制会有所不同。我也明白这是一个运筹学问题,但我没有经验,也不是专业的程序员。
请留下您对特定文献或软件的任何指示。谢谢
python-3.x - 容量约束检查仅在 OR-Tools 中的节点级别
我们将提货配送模块与容量限制相结合。在这里,我们继续在路线上拾取和放下物品(可以在同一个节点上拾取和放下)。因此,即使他的容量较小,一个人也将能够接受更多订单,因为在下一个节点他将丢弃它。
例如:让我们假设:
我们维护了两个数组“ data['pickup_demand'] ”用于拾取节点的需求,“ data['delivery_demand'] ”用于放置节点的需求。我们还减去它以获得最终数据 (即:“ data['demands'] = data['pickup_demand'] - data['delivery_demand'] ”)。
在这里,如果我们看到,即使它是最大的,同一辆车也能够完成这项总任务。重量为10 公斤。
我们不想考虑它承载的所有订单的总重量是多少(即在这里加上所有的皮卡,它是21 公斤)。但是,检查应仅基于节点,其不应大于 10 公斤。通过这种方式,车辆可以完成更多任务。
尽管路由不像上面显示的那样,但是,我们的要求是考虑最大。仅在节点上进行权重检查。
我想,我需要修改这个吗?
r - ompr MILPModel : 二元运算符的非数字参数
我熟悉如何使用 ompr::MIPModel 但我正在尝试学习如何使用 MILPModel 来利用模型构建速度。我的模型的简化版本如下。我有两个决策变量,x 和 y,二进制且长度相等。我对所有 x 决策变量的总和以及所有 y 决策变量的总和都有限制。到目前为止,MILPModel 非常好,我可以构建模型并快速解决它。
问题是当我尝试使用下一个约束时。此约束的 LHS 将 x 二元决策变量乘以相同长度的数据帧中的数字列,然后将其乘以行等于 x 长度的矩阵。RHS 中的类似故事与 y 变量。然后我将这个约束迭代 20 次以表示矩阵的所有列。
我已经多次使用 MIPModel 使用与此类似的约束,但现在当我尝试此操作时,我收到一条错误消息,non-numeric argument to binary operator
. 我认为这与colwise
函数有关,但我不熟悉如何处理这个问题,即使在阅读了 ompr github 站点之后也是如此。提前感谢您的帮助。
scheduling - Ortools中代表forall操作
我正在尝试解决 Ortools 中的生产调度问题。问题包含并行机器。我创建了一个名为 all_task 的变量,就像在https://developers.google.com/optimization/scheduling/job_shop的标准示例中一样,但是我在机器 id 处索引了变量而不是任务 ID
all_tasks[job_id, machine_id] = task_type(start=start_var, end=end_var, interval=interval_var)
现在,在创建约束时,我希望单个作业的所有机器中的间隔总和(生产持续时间)应该等于作业所需的总间隔。我如何在 ortools 中做到这一点?在 Pulp 包中,我可以创建一个for
作业循环,然后for
在第一个 for 循环内的 lpsum 函数内再次创建迭代器。