问题标签 [linear-programming]

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 投票
7 回答
18077 浏览

mathematical-optimization - Java 数学优化库——免费还是开源推荐?

有谁知道这样一个执行数学优化(线性规划、凸优化或更一般类型的问题)的库?我正在寻找类似 MATLAB 的东西,但它能够处理更大的问题。我是否必须编写自己的实现,或购买其中一种商业产品(CPLEX 等)?

0 投票
5 回答
2003 浏览

python - 求解最小值的不等式

我正在研究一个归结为一组方程和不等式的编程问题:

我想解决 的值X将给出 的绝对最小值C,给定输入D和列表,A并且Ba[0 - n]和组成b[0 - n ]

我目前正在用 Python 解决这个问题,但一般来说问题是与语言无关的。

澄清更新:系数x[0 - n]仅限于非负整数集。

0 投票
3 回答
31392 浏览

java - Java的线性编程工具/库

我想建立一个大型线性规划模型来解决一个有趣的问题。我会在 Java 中最舒服。有哪些工具/库可用?

0 投票
2 回答
1788 浏览

matlab - matlabs linprog 太慢了

我正在开发一个需要大大提高速度的 matlab 应用程序。我正在使用 linprog 来求解一个 2 约束线性程序,该程序有大约 10,000 个以零和一为界的变量。Linprog 对我的应用程序来说非常慢。有什么办法可以重新制定以提高速度吗?或者您是否知道一些有用的与 matlab 兼容的共享软件(我的预算很紧)?

0 投票
4 回答
607 浏览

linear-algebra - Linear Programming with Complication

I'm trying to solve a problem that looks like a standard Linear Programming problem with one twist.

We have as input a set of "phrases" each of which has a weight. We need to choose how many times to repeat each phrase in a text to maximize the total weight, subject to a max character length limitation.

This seems like a straightforward linear programming problem, except for the fact that one phrase could be subphrase of another. So for example if your input phrases include "foo bar" and "foo", then if you repeat the phrase "foo bar", you also repeat the phrase "foo". I don't know how to deal with this in a linear programming model.

0 投票
13 回答
56775 浏览

mathematical-optimization - 最佳开源混合整数优化求解器

我正在使用 CPLEX 来解决巨大的优化模型(超过 10 万个变量)现在我想看看我是否可以找到一个开源替代方案,我解决了混合整数问题 (MILP) 并且 CPLEX 效果很好,但是如果我们想要扩展,所以我真的需要找到替代方案或开始编写我们自己的临时优化库(这会很痛苦)

任何建议/见解将不胜感激

0 投票
5 回答
20859 浏览

java - Java 库?- 单纯形/线性规划/优化

我正在寻找一个优化库。我的两个要求是它不使用 JNI,并且它没有许可证限制阻止它在商业上用于多台计算机。我发现满足这些要求的唯一一个是 Choco,但它是无法使用的越野车。

0 投票
9 回答
12401 浏览

algorithm - 分配班次的算法(离散优化问题)

我正在开发一个应用程序,可以优化地为医院的护士分配轮班。我相信这是一个离散变量的线性规划问题,因此可能是 NP-hard:

  • 每天,每位护士(约 15-20 名)都被分配一个轮班
  • 有少量(约 6 个)不同的班次
  • 有相当多的约束和优化标准,无论是与一天有关,还是与员工有关,例如:
    • 每天必须为每个班次分配最少人数
    • 一些班次重叠,因此如果有人在做中间班次,则可以在早期班次少一个人
    • 有些人更喜欢早班,有些人更喜欢晚班,但需要最少的换班才能获得更高的轮班工作工资。
    • 一个人一天不能晚班,第二天早班(由于最低休息时间规定)
    • 会议分配的工作周长度(不同的人不同)
    • ...

所以基本上有大量(大约 20*30 = 600)个变量,每个变量都可以取少量的离散值。

目前,我的计划是使用修改后的最小冲突算法

  • 从随机分配开始
  • 对每个人和每一天都有一个健身功能
  • 选择健身值最差的人或日子
  • 为那一天/人随机选择一项任务,并将其设置为产生最佳适应度值的值
  • 重复直到达到最大迭代次数或对于选定的日期/人无法找到改进

有更好的想法吗?我有点担心它会陷入局部最优。我应该使用某种形式的模拟退火吗?或者不仅考虑一次只改变一个变量,还特别考虑两个人之间的轮班切换(当前手动算法的主要组成部分)?我想避免根据当前的约束来定制算法,因为这些可能会改变。

编辑:没有必要找到严格的最优解;名册目前是手动完成的,我很确定结果在大多数情况下都不是最理想的——应该不难打败它。短期调整和手动覆盖也肯定是必要的,但我不认为这会是一个问题;将过去和手动分配标记为“固定”实际上应该通过减少解决方案空间来简化任务。

0 投票
6 回答
2983 浏览

perl - 如何解决 Perl 中的一组约束?

我在 Perl 中有以下一组约束(只是一组示例约束,不是我真正需要的约束):

我需要找到一个($a, $b, $c)满足约束的列表。我天真的解决方案是

现在,这个解决方案不能保证结束,而且通常效率很低。在 Perl 中有没有更好的方法来做到这一点?

编辑: 我需要这个用于随机测试生成器,因此解决方案需要使用随机函数,例如rand(). 完全确定性的解决方案是不够的,尽管如果该解决方案可以给我一个可能组合的列表,我可以随机选择一个索引:

编辑2: 这里的约束很容易用蛮力解决。但是,如果有许多变量具有很大范围的可能值,那么蛮力不是一种选择。

0 投票
2 回答
1497 浏览

math - 分区中可能的组合数

给定一个大小为 n 的集合 S,它被划分为大小为 n1,..,nk 的类 (s1,..,sk)。自然地,它认为 n = n1+...+nk。

我有兴趣找出可以组合此分区元素的方法的数量,以便每个组合恰好包含每个类的一个元素。

因为我可以从 s1 中选择 n1 个元素,从 s2 中选择 n2 个元素,依此类推,所以我正在为任意 n1,..nk 寻找 max(n1*..*nk) 的解决方案,它持有 n1+..+nk =n。

我感觉这是一个线性优化问题,但是自从我作为本科生学习这些东西以来已经太久了。我希望有人记得如何计算这个。