问题标签 [mathematical-optimization]

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

什么是NP完全问题？为什么它在计算机科学中如此重要？

我正在寻找一种算法来填充具有最短总线长度的矩形，以便给定区域的对象可以通过阴影。

例如，给定一个 5x3 厘米的矩形，我使用 1 厘米宽的平行线进行孵化，我可以通过孵化的最大物体是边长为 1 厘米的正方形。我使用了总共​​ 22 厘米（即 4x3+2x5）的阴影线。因此，为了通过 1 平方厘米的面积，我使用了 22 厘米的孵化线。

该算法应该找到一种模式，使当前 22cm 的整体阴影线最小化，同时不允许超过 1sqcm 的区域通过（对象不必是正方形甚至矩形的形式，重要的是整体区域）。

编辑：在 nlucaroni 的带领下，我发现了蜂窝猜想，该猜想指出，将平面划分为相等面积的区域的周长至少与正六边形网格的周长相同，这部分回答了我的问题。

我目前面临一个困难的排序问题。我有一组事件需要相互排序（比较排序）以及它们在列表中的相对位置。

用最简单的术语来说，我有一个事件列表，每个事件都有一个优先级（整数）、一个持续时间（秒）和事件可以出现在列表中的最早发生时间。我需要根据优先级对事件进行排序，但在其最早发生时间之前，列表中不能出现任何事件。这是一个（希望）使其更清晰的示例：

项目“b”必须排在最后，因为它不允许在进入列表的 6.0 秒后开始，所以它被推迟并且“c”在“b”之前出现，即使它的优先级较低。（希望上面能解释我的问题，如果没有让我知道，我会编辑它。）

我目前的想法是使用插入排序来管理排序过程。与许多其他常见的排序算法不同，插入排序一次一个地决定列表的顺序。因此，对于每个索引，我应该能够找到满足其最早发生时间的下一个最低优先级事件。

我希望找到有关排序算法和数据结构的资源，以帮助我为这种“排序”问题设计一个好的解决方案。我真正的问题实际上比这更复杂：分层排序、事件之间的可变缓冲区、多个非常量时间限制，所以信息或想法越多越好。速度和空间并不是真正的问题。排序的准确性和代码的可维护性是一个问题。

编辑：澄清（基于评论）

• 事件消耗它们的整个持续时间（即不允许事件重叠）
• 事件必须在其最早时间或之后发生，它们不能在其最早时间之前发生。
• 如果存在较低优先级的事件，事件可能会晚于它们的 earlyTime
• 事件不能被打断
• 最长持续时间是可以放入列表中的所有事件的总和。这在上面没有显示。（实际上所有事件的持续时间将远远大于时间列表的最大持续时间。）
• 不能有任何空隙。（没有孔可以尝试回填。）

编辑：回答

虽然 David Nehme 给出了我选择的答案，但我想指出他的答案本质上是插入排序，其他几个人提供了插入排序类型的答案。这向我证实了专门的插入排序可能是要走的路。感谢大家的回答。

我有一个元素数组 ( arr) 和一个函数 ( f)，它接受 2 个元素并返回一个数字。

我需要数组的排列，这样对于每个inf(arr[i], arr[i+1])尽可能少。（它应该循环，即它也应该最小化）iarrf(arr[arr.length - 1], arr[0])

此外，f工作有点像距离，所以f(a,b) == f(b,a)

如果效率太低，我不需要最佳解决方案，但是一个运行合理且速度快的解决方案，因为我需要实时计算它们（我不知道长度arr是多少，但我认为它可能是大约30）

有谁知道 R 的任何优化包（类似于 S+ 的 NUOPT）？

我喜欢研究 AI 优化软件（遗传算法、粒子群、蚁群等）。不幸的是，我已经用完了有趣的问题要解决。你想解决什么问题？

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

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.

我有一个（一阶）ODE 系统，计算导数相当昂贵。

然而，在给定的误差范围内，导数的计算成本要低得多，因为导数是从收敛序列计算的，并且边界可以放在丢弃项的最大贡献上，或者通过使用存储在 kd-tree 中的预先计算的范围信息/octree 查找表。

不幸的是，我还没有找到任何可以从中受益的通用 ODE 求解器；他们似乎都只是给你坐标并想要一个准确的结果。（请注意，我不是 ODE 方面的专家；我熟悉 Runge-Kutta、Numerical Recipies 书中的材料、LSODE 和 Gnu 科学图书馆的求解器）。

即对于我见过的所有求解器，您提供了一个derivs回调函数，接受 at和一个数组x，并返回一个返回数组dx/dt；但理想情况下，我正在寻找一个能提供回调t、xs和一系列可接受的错误，并接收dx/dt_min和dx/dt_max返回数组的方法，其导数范围保证在所需的精度范围内。（可能有许多同样有用的变体）。

任何考虑到这种事情而设计的求解器的指针，或解决问题的替代方法（我不敢相信我是第一个想要这样的东西的人）将不胜感激。