问题标签 [linear-programming]

我正在用 PHP 编写一个小算法，它遍历n部带有评级的电影，并将存储前 5 部。我不是从数据文件中读取，而是从流中读取，所以我不能简单地按评级对电影进行排序。

我的问题是，当我阅读流媒体时，跟踪排名前 5 的电影的最有效方法是什么？目前我执行以下操作：

1. 读入 5 部电影（进入名为 movies[] 的数组），带有两个键 movies[][name] 和 movies[][rating]
2. 使用 array_multisort() 按 movies[rating] 排序数组（最高评分现在位于 movies[4]）
3. 在下一部电影中阅读
4. 如果这个新电影评分 > movies[0][rating] 则用这个新电影替换 movies[0]
5. 重新排序列表
6. 重复 3-5 直到完成

我的方法有效，但每次阅读后都需要对列表进行排序。我相信这是一种昂贵的方法，主要是因为每次我使用 array_multisort() 时，我都必须对 5 部电影进行 for 循环，以构建要排序的索引。谁能提出一个更好的方法来解决这个问题？

有人将 GLPK 用于生产系统吗？我有一个当前由 CPLEX 提供支持的应用程序，并希望将其替换为免费软件替代品。

它用于解决调度问题的大型 MIP（数千个变量）。我想知道 GLPK 是否足够成熟来处理这个问题。

谢谢

我需要单纯形算法的健壮 C++ 源代码（是一种流行的线性规划问题数值解算法）。

请不要链接到维基百科。我需要良好的 C++ 源代码，使用模板，清晰的用户友好名称并且工作得很好。

最好算法必须检查不稳定的浮点计算。

我已将我的问题（表格布局算法）简化为以下问题：

想象一下，我有 N 个变量 X ₁ , X ₂ , ..., X _N。我也有一些（未确定的）不等式，例如：

X ₁ >= 2
x ₂ + X ₃ >= 13
等等。

每个不等式都是一个或多个变量的总和，并且始终使用 >= 运算符将其与常数进行比较。我不能提前说我每次会有多少不等式，但所有变量都必须是非负的，所以每个变量已经是一个。

如何解决这个系统，使变量的值尽可能小？

补充：阅读维基百科文章并意识到我忘了提到变量必须是整数。猜猜这会让它变得 NP 难，对吧？

假设我们有一个 m × n 矩阵 A ，其秩为 m 和一个集合 K⊆{1..n} 使得由 K 索引的 A 的列是线性独立的。现在我们想扩展 K 并找到一个集合 L 使得 k⊆L 和由 L 索引的列也是线性独立的。

一种方法是开始将列索引添加到 K 并测试新集合是否线性独立，例如使用高斯消除。但是有没有更好的方法让我不需要测试添加的每个索引。

谢谢你

我需要为我的应用程序使用整数线性规划 API/工具。虽然我的应用程序是用 Java 编写的，但我不介意从 Java 调用 EXE（工具），使用文件（MPS 等）提供输入。

我的搜索分析如下： 有多种开源和商业工具可用于解决 ILP 以下我发现并认为对我的需求有用。1. Gnu LP Kit(GLPK)：我认为这是最古老的，可能是最稳定和最有效的 2. IP_Solve：对它有很好的评价。3. JavaILP：找到了这个，但没有太多评论 4. Apache Common-Math：支持 LP 但不支持 ILP，所以排除了。5. 硬币或

你能建议哪一个在稳定性、效率、接受度等方面最好

问候

找到一个使 c 最小化的向量 x 。x 受约束 m 。x >= b, x 整数。

这是一个示例输入集：

带输出：

解决此类问题的好工具有哪些，以及如何使用它们的示例？

我正在尝试使用 为 Maxima 中的线性系统编写通用求解器linsolve(eqlist, varlist)，但不必明确指定问题的维度。

这有效，但将尺寸固定为 3：

linsolve( [ eq[0],eq[1],eq[2] ], [ a[0],a[1],a[2] ])

这不会：

关于如何让它发挥作用的任何见解？

---

问题背后的背景：这个线性系统出现在求解整数幂的有限和时，即有限多个平方、立方或一般幂的总和p。尽管有限平方和很简单，但一般解决方案却出奇地复杂：可以在此处找到讨论：递归关系的有限求和，第 2 部分。

我正在开发一个项目，其中包含一些比我习惯的更复杂的界面元素动态布局。我总是觉得编写复杂的代码来检查某某是否接近某某，在这种情况下将其向某个方向移动 x% 等是愚蠢的。这不是编程应该做的方式。编程应该尽可能地声明性！

正是因为我要做的事情相当简单，所以我认为这将是一个尝试新事物的好机会，我想将其NSPredicate用作一个简单的 约束求解器。到目前为止，我只用于NSPredicate非常简单的任务，但我知道它的功能更多。

有什么想法、经验、例子、警告和见解在这里有用吗？

我将举一个非常简单的例子，所以会有一些具体的答案。我该如何NSPredicate解决以下约束：

（“viewB 应该水平居中在坐标 300 上，除非它的左边缘在 viewB 右边缘的 20 像素范围内，在这种情况下，viewA 的左边缘应该固定在 viewB 右边缘右侧 20 像素处，并且 viewA 的水平中心被推到正确的。”）

viewA.rightEdge并且viewB.width可以变化，这些是“输入变量”。

编辑：任何解决方案都可能必须使用NSExpression方法-(id)expressionValueWithObject:(id)object context:(NSMutableDictionary *)context。 这个答案是相关的。

我有一个“连续”线性规划问题，涉及在弯曲凸空间上最大化线性函数。在典型的 LP 问题中，凸空间是多面体，但在这种情况下，凸空间是分段弯曲的——也就是说，它有面、边和顶点，但边不是直的，面也不是平的. 我没有被有限数量的线性不等式指定，而是有一个连续无限的数量。我目前正在通过多面体近似曲面来处理这个问题，这意味着将连续无限的约束离散为非常大的有限数量的约束。

我也处于想知道在对潜在问题的小扰动下答案如何变化的情况。因此，我希望能够根据附近的解决方案为求解器提供初始条件。我相信这种能力被称为“热启动”。

有人可以帮我区分那里的各种 LP 包吗？我并不像速度（对于大量约束）、高精度算术和热启动那样关心用户友好性。

谢谢！

编辑：从到目前为止与问答者的对话来看，我应该更清楚我要解决的问题。一个简化的版本如下：

我有单个实变量 y 的 N 个固定函数 f_i(y)。我想找到 x_i (i=1,...,N) 最小化 \sum_{i=1}^N x_i f_i(0)，受约束：

• \sum_{i=1}^N x_i f_i(1) = 1，并且
• \sum_{i=1}^N x_i f_i(y) >= 0 对于所有 y>2

更简洁地说，如果我们定义函数 F(y)=\sum_{i=1}^N x_i f_i(y)，那么我想在 F(1)=1 的条件下最小化 F(0)，并且F(y) 在整个区间 [2,infinity) 上为正。请注意，后一种积极性条件实际上是对 x_i 的无限数量的线性约束，每个 y 一个。您可以将 y 视为一个标签——它不是一个优化变量。一个特定的 y_0 将我限制在 x_i 的空间中的半空间 F(y_0) >= 0。当我在 2 和无穷大之间改变 y_0 时，这些半空间不断变化，形成一个弯曲的凸形。这种形状的几何形状隐含地（并且以复杂的方式）取决于函数 f_i。